「FJ2014集训」信心题

2014年7月20日3,5110

「题目描述」
在二维平面上有若干个多边形,每个多边形都覆盖了一定的区域,它们之间有可能重
叠,请求出这些多边形遮住了多大的平面区域。
即,求多边形的面积并。
「输入格式」
本题为提交答案题,共有 10 个输入,分别是 cover1.in ∼ cover10.in。
每个文件第一行,一个整数,表示这个输入文件的序号 (1 ∼ 10)。
接下来一行,一个整数 n,表示这组数据中有 n 个多边形。
接下来 n 行,每行第一个整数 Pi,表示这个多边形有 Pi 个点,接下来有 Pi 组整数,
表示这个多边形的 Pi 个点的坐标。
「输出格式」
请编写一个程序,根据提供的文件序号输出相应的答案(保留 5 位小数)。
「样例输入」
0
1
3 0 0 1 0 1 1
「样例输出」
0.50000
「评分标准」
答案与标准答案偏差不超过 2% 的可以获得全部的分数。
答案与标准答案偏差超过 20% 的不得分。
其余情况根据下列公式进行评分:
⌊(1 − 4 ∗
|Usr − Std|
Std ) ∗ 10⌋
「数据规模与约定」
多边形的点的横纵坐标的绝对值 ≤ 108。
多边形数量不超过 106。

「题解」

题交答案题,前4个点为完全没有重合的多边形,直接求面积和

中间2个点为一串一串的旋转45度的正方形,最后用大正方形框起来,实际上是输出大正方形面积,不过可以将坐标旋转后做矩形面积并

最后4个矩形面积并

 

avatar
  Subscribe  
提醒