Description

That day, humanity finally remembered the fear of being ruled by them, and the shame of being imprisoned in a cage.

To protect what she values most, Kiana built $n$ walls. Each wall is closed and forms a convex polygon, and different walls do not intersect each other. For special purposes, the walls are divided into two types: the Craftsman Wall, built from bricks and rocks, and the Natural Wall, formed by trees and thorns.

Relying only on walls is still not reassuring, so Kiana also sent two types of soldiers to patrol inside the walls:

Soul Hunter: They grew up with nature, can pass through Natural Walls freely, but cannot pass through Craftsman Walls.

Pegasus Knight: They can fly in the sky, so they can fly over Craftsman Walls freely, but due to certain beliefs, they cannot pass through Natural Walls.

Even relying on walls and soldiers is still not reassuring, but Kiana also possesses divine power. During a period of time, she used this power $m$ times to perform two kinds of events:

1. Convert a Craftsman Wall into a Natural Wall, or convert a Natural Wall into a Craftsman Wall.

2. Teleport a Soul Hunter or a Pegasus Knight directly to the coordinate $(x,y)$. It is guaranteed that this coordinate is not on any wall, and its distance to the nearest wall is at least $10^{-3}$.

After each soldier teleportation, Kiana wants to know the area of the region where this soldier can move freely. Since she cannot do it, she hopes you can tell her the answer.

Input Format

The first line contains two positive integers $n$ and $m$, representing the number of walls and the number of times Kiana uses divine power. The testdata guarantees $n\leq 3\times 10^4$ and $m\leq 10^5$.

In the next $n$ lines, the $i$-th line describes the $i$-th wall. It starts with two positive integers $k_i$ and $r_i$, representing the number of vertices and the type of this wall. If $r_i=1$, it is a Craftsman Wall; if $r_i=2$, it is a Natural Wall. Then follow $2k_i$ real numbers: the $(2p-1)$-th and $2p$-th numbers are the $x$- and $y$-coordinates of the $p$-th vertex of this wall. All vertices are given in counterclockwise order along the polygon. The testdata guarantees $3\leq k_i\leq 100$ and $\sum_{i=1}^{n}k_i\leq 10^5$.

In the next $m$ lines, the $j$-th line describes the $j$-th use of divine power. It starts with a positive integer $op$, indicating the type of operation. If:

$op=1$: This line also contains a positive integer $u$, meaning Kiana changes the type of wall $u$ (if it is originally a Craftsman Wall, it becomes a Natural Wall; if it is originally a Natural Wall, it becomes a Craftsman Wall). The testdata guarantees $1\leq u\leq n$.

$op=2$: This line also contains a positive integer $v$ and two real numbers $x$ and $y$. If $v=1$, Kiana teleports a Soul Hunter to $(x,y)$; if $v=2$, Kiana teleports a Pegasus Knight to $(x,y)$.

The testdata guarantees that all $r_i$, $op$, and $v$ take values only $1$ or $2$. All real numbers are given with exactly two digits after the decimal point and have absolute value less than $2\times 10^5$. The distance between any two polygons is at least $10^{-3}$. For any two input vertices, the absolute value of the difference in their $x$-coordinates and the absolute value of the difference in their $y$-coordinates are both at least $10^{-3}$.

Output Format

The output consists of several lines. For each input with $op=2$, output one line with a real number $S$ (rounded to $4$ digits after the decimal point), representing the area of the region where the soldier can move freely. The testdata guarantees that this area is finite.

3 5
4 1 -10.10 -10.20 10.30 -10.40 10.50 10.60 -10.70 10.80
4 2 -20.80 -20.70 20.60 -20.50 20.40 20.30 -20.20 20.10
4 1 -30.10 -30.30 30.50 -30.70 30.20 30.40 -30.60 30.80
2 1 15.80 15.60
2 1 25.40 25.20
1 2
2 1 15.70 15.50
2 1 25.30 25.10

3271.8500
3271.8500
1236.0000
2035.8500

Hint

From the 2018 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2018). Thanks to Pony.ai for supporting this contest.

Solutions and other resources can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5