题目描述

注意：本题答案数据并非来自原比赛，并且改变了比较方式，更多细节请参考题目最后「修订」一节。

那一天，人类终于回想起，曾经一度被她们支配的恐惧，还有被囚禁于鸟笼中的那份耻辱。

为了守护最珍视之物，Kiana 建立起了 $n$ 座围墙，每一座围墙都闭合形成了一个凸多边形，不同的围墙互不相交。出于特别的目的，围墙分为两种：

• 工匠之墙：用砖瓦和岩石砌成
• 自然之墙：用树木和荆棘形成

Kiana 还派遣了两类士兵在墙内巡逻：

• 追魂猎人：可以自由穿越自然之墙，但无法通过工匠之墙
• 天马骑士：可以自由飞越工匠之墙，但无法通过自然之墙

Kiana 还拥有神之力量，在某段时间内，她发挥了 $m$ 次这股力量，以完成两类事件：

1. 将某座工匠之墙转化为自然之墙，或将某座自然之墙转化为工匠之墙
2. 将一位追魂猎人或天马骑士直接传送到坐标 $(x,y)$ 处，保证这个坐标不位于围墙之上，且与最近的围墙相距至少 $10^{-3}$

在每一次传送士兵完成后，Kiana 希望知道这名士兵可以自由活动的区域面积有多大。

---

输入格式

第一行包含两个正整数 $n$ 和 $m$，分别表示围墙的数量和发动神之力量的次数。

数据保证 $n \leq 3 \times 10^4$ 且 $m \leq 10^5$。

接下来 $n$ 行，第 $i$ 行描述第 $i$ 座围墙的情况：

• 两个正整数 $k_i$ 和 $r_i$
• 若 $r_i = 1$ 表示这是工匠之墙，若 $r_i = 2$ 表示这是自然之墙
• 接下来 $2k_i$ 个实数，第 $2p-1$ 和第 $2p$ 个数表示这座围墙上第 $p$ 个顶点的横、纵坐标

所有的顶点按照在多边形上逆时针排列的顺序输入。

数据保证 $3 \leq k_i \leq 100$ 且 $\sum_{i=1}^{n} k_i \leq 2 \times 10^5$。

接下来 $m$ 行，第 $j$ 行描述第 $j$ 次使用神之力量的情况：

• 一个正整数 $\text{op}$，表示神之力量类型

若：

• $\text{op} = 1$：这一行还有一个正整数 $u$，表示转换了第 $u$ 座围墙的类型
• $\text{op} = 2$：这一行还有一个正整数 $v$ 与两个实数 $x$ 和 $y$
  • 若 $v = 1$，表示将一名追魂猎人传送到 $(x,y)$ 处
  • 若 $v = 2$，表示将一名天马骑士传送到 $(x,y)$ 处

数据保证：

• 所有的 $r_i$、$\text{op}$ 和 $v$ 的取值仅为 $1$ 或 $2$
• 所有的实数保留到小数点后两位且绝对值小于 $2 \times 10^5$
• 任意两个多边形之间的距离至少为 $10^{-3}$
• 任意两个输入顶点的横坐标之差与纵坐标之差的绝对值不小于 $10^{-3}$

---

输出格式

对于每个 $\text{op} = 2$ 的输入，输出一行一个实数 $S$（保留到小数点后 $4$ 位），表示该名士兵可以自由活动的区域面积。

数据保证这个面积是有限的。

若你的输出与答案输出之间的绝对误差或相对误差不超过 $10^{-4}$，则认为你的输出是正确的。

---

样例

输入

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

---

数据范围与提示

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。

---

修订

由于原比赛 repo 提供的数据中答案输出有误，联系出题人请求正确输出未果，因此根据 @HeRaNO 的代码重新制作输出数据。如有问题请联系 @HeRaNO。