【NOI2017】分身术 排行榜


时间限制: 3 s
空间限制: 512 MB

题目描述

"分!身!术!" —— 小P

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

"分!身!术!"

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

输入格式

从标准输入读入数据。

输入第一行包含两个正整数 $n, m$,描述初始时分身的个数,和总时刻数。

接下来 $n$ 行,第 $i$ 行有两个整数 $x_i, y_i$ ,描述第 $i$ 个分身的位置。

接下来 $m$ 行,每行的第一个整数 $k$ 表示这一时刻有 $k$ 个分身消失。接下来有 $k$ 个非负整数 $c_1,c_2,\cdots c_k$,用于生成消失的分身的编号。

生成方式如下:

设上一个时刻中,分身占领面积的两倍为 $S$。则该时刻消失的分身 $p_{1}, p_{2}, \dots, p_{k}$ 的编号为:

$$p_i = [(S + c_i) ~\mathrm{mod}~ n] + 1$$

特别的,在第一个时刻,我们认为上一个时刻中, $S=-1$ ,即:第一个时刻消失的分身 $p_{1}, p_{2}, \dots, p_{k}$ 的编号为:

$$p_i = [(-1+c_i) ~\mathrm{mod}~ n] + 1$$

输出格式

输出到标准输出。

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

样例输入

样例输出

数据范围

测试点编号$n$$m$$k$
11010$\leq n - 3$
210001000
3
4
5100000100000$=1$
6
7
8
9$=2$
10
11$\leq 3$
12$\leq 5$
13$\leq 9$
14$\leq 12$
15$\leq 20$
16$\leq 100$
17
18
19
20

对于所有数据,保证:

题目来源

NOI 2017 Day 2


关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。




Judge Duck Online | 评测鸭在线
Server Time: 2019-10-16 22:05:34 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用