题目描述

平面上有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

提示

没有写明提示

题目来源

没有写明来源