P3827 [NOI2017] Clone Technique

"Clone! Technique!" — Xiao P. On a plane, there are $n$ clones of Xiao P. Define the region occupied by a set of clones as the smallest convex polygon that covers this set of clones (i.e., the convex hull). Xiao P's ability is limited: at each time step, several clones will disappear. However, before the next time step, Xiao P will use the Clone Technique to make these disappeared clones reappear at their original positions. Xiao P wants to know the area of the region occupied by the remaining clones after the disappearances at each time step. Constraints - $|x_i|, |y_i| \le 10^8$. - No two clones share exactly the same coordinates. - $k \le 100$. - The sum of $k$ over all time steps does not exceed $2 \times 10^6$. - $0 \le c_i \le 2^{31} - 1$. - Initially, the area occupied by all $n$ clones is greater than $0$. - Define the vertex set of the region occupied by all $n$ clones as $S$, with $|S| \ge 3$. At any time step, there exist at least two clones from $S$ that have not disappeared. | Test point ID | $n \leq$ | $m \leq$ | $k$ | | :-----------: | :------: | :------: | :--------: | | $1$ | $10$ | $10$ | $\leq n-3$ | | $2$ | $10^3$ | $10^3$ | $\leq n-3$ | | $3$ | $10^3$ | $10^3$ | $\leq n-3$ | | $4$ | $10^3$ | $10^3$ | $\leq n-3$ | | $5$ | $10^5$ | $10^5$ | $=1$ | | $6$ | $10^5$ | $10^5$ | $=1$ | | $7$ | $10^5$ | $10^5$ | $=1$ | | $8$ | $10^5$ | $10^5$ | $=1$ | | $9$ | $10^5$ | $10^5$ | $=2$ | | $10$ | $10^5$ | $10^5$ | $=2$ | | $11$ | $10^5$ | $10^5$ | $\leq 3$ | | $12$ | $10^5$ | $10^5$ | $\leq 5$ | | $13$ | $10^5$ | $10^5$ | $\leq 9$ | | $14$ | $10^5$ | $10^5$ | $\leq 12$ | | $15$ | $10^5$ | $10^5$ | $\leq 20$ | | $16$ | $10^5$ | $10^5$ | $\leq 100$ | | $17$ | $10^5$ | $10^5$ | $\leq 100$ | | $18$ | $10^5$ | $10^5$ | $\leq 100$ | | $19$ | $10^5$ | $10^5$ | $\leq 100$ | | $20$ | $10^5$ | $10^5$ | $\leq 100$ |

The first line contains two positive integers $n, m$, denoting the initial number of clones and the total number of time steps. The next $n$ lines each contain two integers $x_i, y_i$, describing the position of the $i$-th clone. The next $m$ lines: on each line, the first integer $k$ indicates that $k$ clones disappear at this time step. Then there are $k$ non-negative integers $c_1, c_2, \ldots, c_k$, used to generate the indices of the disappearing clones. Generation method: Let $S$ be twice the area of the region occupied by the clones at the previous time step. Then the indices of the clones that disappear at this time step, $p_1, p_2, \ldots , p_k$, are: $p_i = [(S + c_i) \bmod n] + 1$. In particular, at the first time step we assume $S = -1$, i.e., the indices of the clones that disappear at the first time step, $p_1, p_2, \ldots , p_k$, are: $p_i = [(−1 + c_i) \bmod n] + 1$.

Output $m$ lines in the order of the time steps. Each line contains one integer: twice the area of the region occupied by the remaining clones at that time step.

Sample explanation: As shown in the figure: the left figure shows the positions of the $6$ clones and the region they occupy; the middle figure shows the situation at the first time step, where the indices of the disappearing clones are $1, 3, 6$. The remaining $3$ points occupy the region inside the solid lines in the figure, and twice the area is $3$. The right figure shows the situation at the second time step, where the indices of the disappearing clones are $[(0 + 3)\bmod 6] + 1 = 4$ $[(1 + 3)\bmod 6] + 1 = 5$ The remaining $4$ points occupy the region inside the solid lines in the figure.  Translated by ChatGPT 5