[Pa2013]Działka
时间限制：150s 空间限制：512MB
题目描述
平面上有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
提示
没有写明提示
题目来源
没有写明来源