[Pa2013]Dzialka

时间限制: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

提示

没有写明提示


题目来源

没有写明来源