Convex Hull Area Queries in a k x k Plane

You are given a k×k plane with n points and m queries. In each query, a rectangle with sides parallel to the coordinate axes is given, and you need to compute the area of the convex hull of all points (including those on the boundary) that lie inside the rectangle. If there are fewer than 3 points inside the rectangle or if they are collinear, the area is considered to be 0.

Note: If a mathematical formula is required in your explanation, use LaTeX format. For example, the area \(A\) of a polygon given by vertices \((x_i, y_i)\) for \(i=1 \ldots k\) (ordered cyclically) is computed by

[ A = \frac{1}{2}\Big|\sum_{i=1}^{k}(x_i y_{i+1} - x_{i+1} y_i)\Big| ]

You need to output one number per query, which is the area of the convex hull for that query. Print the answer as a floating point number.

inputFormat

The input begins with a single line containing three integers k, n and m, where k describes the size of the plane, n is the number of points, and m is the number of queries. The next n lines each contain two integers x and y representing the coordinates of a point. The following m lines each contain four integers x1, y1, x2 and y2, representing a query rectangle with sides parallel to the coordinate axes. The edges of the rectangle are included in the query.

outputFormat

For each query, output a single line containing the area of the convex hull of the points inside (or on) the query rectangle. If there are fewer than 3 points, output 0. The output should be a floating-point number.

sample

10 4 2
1 1
2 2
3 3
4 4
0 0 5 5
2 2 2 2

0.0
0.0