#P5452. [THUPC2018] 琪亚娜之墙

[THUPC2018] 琪亚娜之墙

题目描述

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

为了守护最珍视之物,Kiana建立起了 nn 座围墙,每一座围墙都闭合形成了一个凸多边形,不同的围墙互不相交。出于特别的目的,围墙分为两种:用砖瓦和岩石砌成的工匠之墙、用树木和荆棘形成的自然之墙

只依靠墙壁并不使人放心,Kiana还派遣了两类士兵在墙内巡逻:

追魂猎人:他们从小与大自然为伴,可以自由穿越自然之墙,但无法通过工匠之墙。

天马骑士:他们拥有在天空中飞行的能力,可以自由飞越工匠之墙,但由于某些信仰的缘故,无法通过自然之墙。

只依靠墙壁和士兵任然难以让人放心,但Kiana还拥有神之力量,在某段时间内,她发挥了 mm 次这股力量,以完成两类事件:

  1. 将某座工匠之墙转化为自然之墙,或将某座自然之墙转化为工匠之墙。

  2. 将一位追魂猎人或天马骑士直接传送到坐标 (x,y)(x,y) 处,保证这个坐标不位于围墙之上,且与最近的围墙相距至少 10310^{-3}

在每一次传送士兵完成后,Kiana希望知道这名士兵可以自由活动的区域面积有多大。由于她不会做,所以希望你来告诉她答案。

输入格式

输入第一行包含两个正整数 nnmm,分别表示围墙的数量和Kiana发动神之力量的次数,数据保证 n3×104n\leq 3\times 10^4m105m\leq 10^5

接下来 nn 行,第 ii 行用于描述第 ii 座围墙的情况,首先有两个正整数 kik_irir_i,分别表示这座围墙的顶点数和类型,若 ri=1r_i=1 表示这是工匠之墙,若 ri=2r_i=2 表示这是自然之墙,接下来 2ki2k_i 个实数,第 2p12p-1 和第 2p2p 个数表示这座围墙上第 pp 个顶点的横、纵坐标,所有的顶点按照在多边形上逆时针排列的顺序输入,数据保证 3ki1003\leq k_i\leq 100i=1nki105\sum_{i=1}^{n}k_i\leq 10^5

接下来 mm 行,第 jj 行用于描述Kiana第 jj 次使用神之力量的情况,首先有一个正整数 opop,表示Kiana发动的神之力量类型,若:

op=1op=1:这一行还有一个正整数 uu,表示Kiana转换了第 uu 座围墙的类型(若本来为工匠之墙,则转化为自然之墙,若本来为自然之墙,则转化为工匠之墙),数据保证 1un1\leq u\leq n

op=2op=2:这一行还有一个正整数 vv 与两个实数 xxyy,若 v=1v=1,表示Kiana将一名追魂猎人传送到了 (x,y)(x,y) 处,若 v=2v=2,表示Kiana将一名天马骑士传送到了 (x,y)(x,y) 处。

数据保证所有的 rir_iopopvv 的取值仅为 1122,所有的实数保留到小数点后两位且绝对值小于 2×1052\times 10^5,任意两个的多边形之间的距离至少为 10310^{-3},任意两个输入顶点的横坐标之差与纵坐标之差的绝对值不小于 10310^{-3}

输出格式

输出由若干行组成,对于每个 op=2op=2 的输入,输出一行一个实数 SS(保留到小数点后 44 位),表示该名士兵可以自由活动的区域面积,数据保证这个面积是有限的。

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 查看。