#2307. 「NOI2017」分身术

内存限制:768 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: April_AA

题目描述

"分!身!术!" ——小 PP

平面上有 nn 个小 PP 的分身。定义一组分身占领的区域为覆盖这组分身的最小凸多边形。小 PP 能力有限,每一时刻都会有若干分身消失。但在下一时刻之前,小 PP 会使用

"分!身!术!"

使得这些消失的分身重新出现在原来的位置。小 PP 想知道,每一时刻分身消失后,剩下的分身占领的区域面积是多少?

输入格式

输入第一行包含两个正整数 nn mm ,描述初始时分身的个数,和总时刻数。
接下来 nn 行,第 ii 行有两个整数 xix_i , yiy_i ,描述第 ii 个分身的位置。
接下来 mm 行,每行的第一个整数 kk 表示这一时刻有 kk 个分身消失。接下来有 kk 个非负整数 c1c_1 , c2c_2 ,... ckc_k ,用于生成消失的分身的编号。
生成方式如下:
设上一个时刻中,分身占领面积的两倍为 SS 。则该时刻消失的分身 p1p_1 , p2p_2 ,... pkp_k 的编号为 :

pi=[(S+ci)modn]+1 p_i = [(S + c_i)\mod n] + 1

特别的,在第一个时刻,我们认为上一个时刻中,S=1S = -1 ,即:第一个时刻消失的分身 p1p_1 , p2p_2 ,... pkp_k 的编号为:

pi=[(1+ci)modn]+1 p_i = [(-1 + c_i)\mod n] + 1

输出格式

按给出时刻的顺序依次输出 mm 行,每行一个整数,表示该时刻剩余分身所占领区域面积的两倍。

样例

样例输入1

6 2
-1 0
-1 -1
0 -1
1 0
0 1
0 0
3 1 3 6
2 0 1

样例输出1

3
2

样例1解释

如下图所示:左图表示输入的 66 个分身的位置及它们占领的区域;中图表示第一个时刻的情形,消失的分身编号分别为 1,3,6,1,3,6, 剩余 33 个点占领图中实线内部区域,占据面积的两倍为 33 ;右图表示第二个时刻的情形,消失的分身编号分别为:

[(0+3)mod6]+1=4 [(0 + 3)\mod 6] + 1 = 4

[(1+3)mod6]+1=5 [(1 + 3)\mod 6] + 1= 5

剩余的 44 个点占领图中实线内部区域。 TIM图片20170721203208.png

数据范围与提示

对于所有数据,保证:

  • xi,yi108|x_i| ,|y_i| \leq 10^8
  • 没有两个分身的坐标是完全相同的;
  • k100k\leq 100
  • 所有时刻的 kk 之和不超过 2×1062\times 10^6
  • 0ci23110\leq c_i \leq 2^{31} - 1
  • 初始时,所有的 nn 个分身占据区域面积大于 00
  • 定义所有 nn 个分身所占据区域的 顶点集合SS , S3S\geq 3 。在任意时刻中, SS 中至少存在两个未消失的分身。

由于 64 位操作系统的指针大小为 8 字节,在 LOJ 上将空间限制扩大为 768MB768\mathrm{MB}