#P3683. [CERC2016] 地理哈希网格 Geohash Grid

[CERC2016] 地理哈希网格 Geohash Grid

题目描述

“地理哈希”是一个将二维平面坐标编码为整数的过程,这将为数据库中地理数据的存储和查询带来方便。在这个问题中,一个地图是一个建立在标准二维笛卡尔坐标系上的2^n行2^n列的矩形网格,越往右x坐标越大,越往上y坐标越大。一个地图格子是一个单位正方形,满足其左下角的点的坐标为(x,y),其中0<=x,y<2^n。

在2^n行2^n列的地图上一共有2^(2n)个格子。对于一个格子c,它的地理哈希值h(c)是一个2n位的非负二进制整数。从最高位开始考虑整个地图,然后重复下面两个步骤n次,即可得到c的地理哈希值h(c):

1.把地图分成左右两个面积相等的区域,如果格子c在左半边,那么这一位是0,否则是1。然后将考虑范围缩小到c所在的那半边地图。

2.把地图分成上下两个面积相等的区域,如果格子c在下半边,那么这一位是0,否则是1。然后将考虑范围缩小到c所在的那半边地图。

一个“地理哈希区间”[a,b]表示所有哈希值在[a,b]之间的格子。通常应用中,我们会用一些地理哈希区间去近似表示地图。给定一个格子集合C,以及一个正整数t,那么C的最优t近似是指使用不超过t个地理哈希区间,覆盖住所有C中的格子(覆盖其它格子是允许的),同时满足覆盖住的区域的面积最小。

给定一个地图以及一个格子集合C,C用一个边平行于坐标轴的简单多边形来表示。然后给定q个询问t_1,t_2,...,t_q,对于每个询问t_k,你需要求出C的最优t_k近似覆盖住的区域的面积。

输入格式

第一行包含一个正整数n(1<=n<=30),表示地图的尺寸的以2为底的对数。

第二行包含一个正整数m(4<=m<=200),表示多边形顶点的个数。

接下来m行,每行两个整数x_i,y_i(0<=x_i,y_i<=2^n),按逆时针依次表示多边形每个顶点的坐标。

输入数据保证多边形不自交,边平行于坐标轴,且不存在相邻两条边是平行的。

接下来一行包含一个正整数q(1<=q<=100000),表示询问的个数。

接下来q行,每行一个正整数t_1,t_2,...,t_q(1<=t_i<=10^9),依次表示每个询问。

输出格式

输出q行,每行一个正整数,依次回答每个询问。

3 8
1 1
5 1
5 4
3 4
3 8
0 8
0 5
1 5
4 2 3 5 7
32
30
26
24

提示

区间[3,29]、[33,33]和[36,37]组成最优3近似,其覆盖住的总面积为30。