#P18289. Ancient Maps, Hidden Danger
Ancient Maps, Hidden Danger
Ancient Maps, Hidden Danger
勇士 Alan 想用地图衡量迷宫的危险程度:有些地方虽然能够走到,却无法从建筑外部直接看见。他希望知道这些区域的总面积。
地图位于二维平面上,由若干堵墙组成。每堵墙是一个没有洞的实心简单多边形;墙的内部和边界都阻挡移动和视线。不同墙没有任何公共点。
不在任何墙内的点称为可到达的点。对于这样的点 ,如果对任意半径 ,都能在以 为圆心、 为半径的圆上找到一个点 ,使得线段 不与任何墙相交,则称 可以从外部看见。否则,称 被隐藏。
求所有可到达且被隐藏的点构成的区域的总面积。墙自身的面积不计入答案。

原题图 A.1:样例 1 的地图。棕色部分是实心墙,灰色部分是可到达但被隐藏的区域。
输入格式
第一行一个整数 ,表示墙的数量。
接下来 行,每行先给出一个整数 ,随后给出 个整数
表示第 堵墙的各个顶点。顶点按顺时针或逆时针顺序给出,最后一个顶点与第一个顶点之间也有一条边。
保证:
- ;
- ,并且 ;
- ,所有坐标都是整数;
- 整个输入中没有重复顶点;
- 每个多边形都是无洞、无自交的简单多边形;
- 不同多边形的内部及边界均不相交。
输出格式
输出一个实数,表示可到达且被隐藏的区域的总面积。答案的绝对误差或相对误差不超过 即可。
样例 1
2
8 0 0 7 0 7 7 6 7 6 1 1 1 1 7 0 7
4 2 7 5 7 5 6 2 6
2.25
样例 2
2
4 2 4 5 8 9 4 5 7
4 4 5 5 1 6 5 5 4
1.4