← 返回题目列表

Codeforces · 814/D

D. 迪斯科舞厅的通宵舞蹈

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

迪斯科舞厅的拥挤永远不会阻止我们的朋友们玩得开心,但宽敞一点也不会有坏处,不是吗?

迪斯科舞厅可以看作是一个无限的xy平面,其中共有n个舞者。一旦有人开始移动,他们只会在自己的移动范围内移动,该范围是一个由中心(xi,yi)和半径ri描述的圆形区域Ci。没有两个范围的边界具有多个公共点,即对于每一对 (i, j) (1 ≤ i < j ≤ n),范围 Ci 和 Cj 是不相交的,或者其中一个是另一个的子集。请注意,两个范围的边界可能共享一个公共点,但没有两个舞者具有完全相同的范围。

月日就是其中之一,它将宽敞度定义为由正在移动的舞者的奇数个移动范围所覆盖的区域。下面显示了一个示例,阴影区域代表每个人同时移动时的宽敞程度。

但是一整夜毕竟没有人继续动,所以一整夜的时间被分成了两半——午夜之前和午夜之后。每个舞者都在一侧走来走去,而另一侧则与朋友们坐在一起。两半的空间是分别计算的,它们的总和当然应该尽可能大。下图显示了上述示例的最佳解决方案。

通过谁在上半场跳舞和谁在下半场跳舞的不同计划,可以实现两个半场不同的空间总和。您要找出该总和的最大可实现值。

输入

输入的第一行包含一个正整数 n (1 ≤ n ≤ 1 000) — 舞者的数量。

下面n行每行描述一个舞者:其中第i行包含三个空格分隔的整数xi、yi和ri(- 106≤xi,yi≤106,1≤ri≤106),描述以(xi,yi)为中心,半径为ri的圆周运动范围。

输出

输出一位十进制数——两半夜内可达到的最大空间总和。

如果输出的相对或绝对误差最多为 10 - 9,则输出被认为是正确的。正式地,让您的答案为 a,陪审团的答案为 b。如果 $$\frac{|a-b|}{\max(1, |b|)} \leq 10^{-9}$$,则认为您的答案是正确的。

示例

输入 #1

5
2 1 6
0 4 1
2 -1 3
1 -2 1
4 -1 1

输出 #1

138.23007676

输入 #2

8
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8

输出 #2

289.02652413

注意

第一个示例对应于图例中的插图。