← 返回题目列表

Codeforces · 107/E

E. 飞镖

中文机器翻译题面 查看原题

毕业典礼后的晚上,开罗德国大学(GUC)的研究生正在玩飞镖。由于没有真正的飞镖靶,因此使用了 GUC 高层管理人员的照片。

所以,墙上放了n张长方形的照片。它们可以任意重叠,甚至重合。照片不一定水平或垂直放置,也可以在固定在墙上之前旋转它们。

一次飞镖投掷的分数就是飞镖经过的照片数量。

Fatma 投掷了一次,但她的得分未记录。她只记得她确实把它拍进了至少一张照片。

假设整个墙上投掷的概率分布是相等的,那么 Fatma 的得分期望是多少?

输入

输入的第一行包含整数 n (1 ≤ n ≤ 500) — 墙上的照片数量。然后n行描述照片,每行包含8个单空格分隔的整数(4个顶点的坐标):x1,y1,x2,y2,x3,y3,x4,y4。每张照片都是一个具有非零区域的矩形。坐标是整数,绝对值不超过104。矩形的坐标按顺时针或逆时针顺序给出。

输出

打印投掷的预期得分。如果绝对误差或相对误差不超过 10 - 6,答案将被接受。

示例

输入 #1

1
0 0 0 2 2 2 2 0

输出 #1

1.0000000000

输入 #2

1
-1 0 0 1 1 0 0 -1

输出 #2

1.0000000000

输入 #3

4
0 0 0 1 3 1 3 0
0 0 0 3 1 3 1 0
3 3 2 3 2 0 3 0
3 3 3 2 0 2 0 3

输出 #3

1.5000000000

输入#4

2
-1 0 0 1 1 0 0 -1
0 0 1 1 2 0 1 -1

输出#4

1.1428571429