P3683 [CERC2016] Geohash Grid

A "geohash" encodes 2D planar coordinates into integers, which facilitates storing and querying geographic data in databases. In this problem, a map is a $2^n \times 2^n$ rectangular grid built on the standard 2D Cartesian coordinate system, where $x$ increases to the right and $y$ increases upward. A map cell is a unit square whose lower-left corner has integer coordinates $(x, y)$, where $0 \le x, y < 2^n$. There are $2^{2n}$ cells on the $2^n \times 2^n$ map. For a cell $c$, its geohash value $h(c)$ is a non-negative $2n$-bit binary integer. Starting from the most significant bit and considering the entire map, repeat the following two steps $n$ times to obtain $h(c)$: 1. Split the map into left and right regions of equal area. If cell $c$ lies in the left half, this bit is $0$; otherwise it is $1$. Then restrict the scope to the half that contains $c$. 2. Split the map into bottom and top regions of equal area. If cell $c$ lies in the bottom half, this bit is $0$; otherwise it is $1$. Then restrict the scope to the half that contains $c$. A "geohash interval" $[a, b]$ denotes all cells whose hash values lie in $[a, b]$ (inclusive). In practice, we approximate a set on the map using a few geohash intervals. Given a set of cells $C$ and a positive integer $t$, the optimal $t$-approximation of $C$ is to use at most $t$ geohash intervals to cover all cells in $C$ (covering other cells is allowed) while minimizing the total covered area. You are given a map and a cell set $C$, where $C$ is represented by a simple polygon whose edges are parallel to the coordinate axes. Then you are given $q$ queries $t_1, t_2, \ldots, t_q$. For each query $t_k$, you need to output the area of the optimal $t_k$-approximation that covers $C$.

The first line contains a positive integer $n$ $(1 \le n \le 30)$, the base-2 logarithm of the map size. The second line contains a positive integer $m$ $(4 \le m \le 200)$, the number of polygon vertices. Each of the next $m$ lines contains two integers $x_i, y_i$ $(0 \le x_i, y_i \le 2^n)$, giving the coordinates of the polygon’s vertices in counterclockwise order. The input guarantees that the polygon is simple, its edges are parallel to the coordinate axes, and no two consecutive edges are parallel. The next line contains a positive integer $q$ $(1 \le q \le 100000)$, the number of queries. Each of the next $q$ lines contains a positive integer $t_i$ $(1 \le t_i \le 10^9)$, the parameter of a query.

Output $q$ lines. For each query, output a single positive integer: the answer to that query.

 The intervals $[3, 29]$, $[33, 33]$, and $[36, 37]$ form an optimal $3$-approximation, whose total covered area is $30$. Translated by ChatGPT 5