P6818 [PA 2013] Działka

Given $n$ points on a $k \times k$ plane and $m$ queries, for each query, find the area of the convex hull formed by the points inside (including the boundary) an axis-aligned rectangle.

The first line contains two positive integers $k, n$. The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th point. Then a line contains one integer $m$. The next $m$ lines each contain four numbers $a_i, b_i, c_i, d_i$, representing a query rectangle with bottom-left corner $(a_i, c_i)$ and top-right corner $(b_i, d_i)$.

For each query, output one line with the area. Keep one digit after the decimal point.

$1 \leq k \leq 10^6$, $3 \leq n \leq 3 \times 10^3$, $1 \leq m \leq 10^6$, $0 \leq x_i, y_i, a_i, b_i, c_i, d_i \leq k$, $a_i < c_i, b_i < d_i$. Translated by ChatGPT 5