← 返回题目列表

Codeforces · 62/C

C. 调查

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

在中世纪,存在着将女巫和她们的宠物黑猫一起烧死在牛排上的传统。到 15 世纪末,黑猫的数量已不复存在。形势的困难导致了紧急调查委员会(EIC)的成立。

决议 #666 规定,当且仅当白猫的黑点周长超过可接受的标准时,白猫才被视为黑色。但可接受的标准等于什么?每个审判官都会根据情况自行选择。你的任务是找到猫皮毛上黑点的周长。

同样的分辨率表明猫的皮毛是一个长度为 105 的白色正方形。在测量斑点时,习惯上将皮毛的左下角放在轴原点 (0;0) 上,将右上角放在坐标原点 (105;105) 上。猫的斑点是非退化三角形。斑点可以相互交叉和重叠,但保证每对三角形斑点的边不超过一个公共点。

我们将这个问题中的周长视为猫的毛皮变色处的边界的总长度。

输入

第一个输入行包含单个整数 n (0 ≤ n ≤ 100)。它是猫毛皮上斑点的数量。最后 n 行的第 i 行包含 6 个整数:x1i、y1i、x2i、y2i、x3i、y3i。它们是第 i 个三角形点的坐标 (0 < xji, yji < 105)。

输出

打印一个数字,问题的答案,三角形并集的周长。您的答案与正确答案的误差不应超过 10 - 6。

示例

输入 #1

1
1 1 2 1 1 2

输出 #1

3.4142135624

输入 #2

3
3 3 10 3 3 10
1 1 9 4 5 6
2 2 11 7 6 11

输出 #2

37.7044021497