3839. [Pa2013]Działka
#3839. [Pa2013]Działka
题目描述
平面上有n个不重复的点。每次询问一个边平行坐标轴的矩形内（包含边界）的点组成的凸包的面积。
输入格式
第一行两个整数k,n(1<=k<=1000000,3<=n<=3000)。
接下来n行，每行两个整数x_i,y_i(0<=x_i,y_i<=k)，表示点的坐标。
接下来一行一个整数m(1<=m<=1000000)，表示询问数量。
接下来m行，每行四个整数a,b,c,d(0<=a<b<=k,0<=c<d<=k)，表示询问的矩形范围为a<=x<=b,c<=y<=d。
输出格式
对于每个询问输出一行表示面积。保留小数点后一位。
样例
样例输入
9 7
1 1
1 3
3 3
3 1
6 5
6 6
7 3
3
0 4 0 4
2 7 0 7
3 7 3 6
样例输出
4.0
10.0
6.0