#P18289. Ancient Maps, Hidden Danger

Ancient Maps, Hidden Danger

Ancient Maps, Hidden Danger

勇士 Alan 想用地图衡量迷宫的危险程度:有些地方虽然能够走到,却无法从建筑外部直接看见。他希望知道这些区域的总面积。

地图位于二维平面上,由若干堵墙组成。每堵墙是一个没有洞的实心简单多边形;墙的内部和边界都阻挡移动和视线。不同墙没有任何公共点。

不在任何墙内的点称为可到达的点。对于这样的点 PP,如果对任意半径 r>0r>0,都能在以 PP 为圆心、rr 为半径的圆上找到一个点 QQ,使得线段 PQPQ 不与任何墙相交,则称 PP 可以从外部看见。否则,称 PP 被隐藏。

求所有可到达且被隐藏的点构成的区域的总面积。墙自身的面积不计入答案。

样例1的原图

原题图 A.1:样例 1 的地图。棕色部分是实心墙,灰色部分是可到达但被隐藏的区域。

输入格式

第一行一个整数 nn,表示墙的数量。

接下来 nn 行,每行先给出一个整数 kik_i,随后给出 2ki2k_i 个整数

x1,y1,x2,y2,…,xki,yki,x_1,y_1,x_2,y_2,\ldots,x_{k_i},y_{k_i},

表示第 ii 堵墙的各个顶点。顶点按顺时针或逆时针顺序给出,最后一个顶点与第一个顶点之间也有一条边。

保证:

  • 1≤n≤301\le n\le30;
  • 3≤ki≤903\le k_i\le90,并且 ∑iki≤90\sum_i k_i\le90;
  • −104≤xj,yj≤104-10^4\le x_j,y_j\le10^4,所有坐标都是整数;
  • 整个输入中没有重复顶点;
  • 每个多边形都是无洞、无自交的简单多边形;
  • 不同多边形的内部及边界均不相交。

输出格式

输出一个实数,表示可到达且被隐藏的区域的总面积。答案的绝对误差或相对误差不超过 10−610^{-6} 即可。

样例 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