English · Original
Chinese · Translation
Formal · Original
The crowdedness of the discotheque would never stop our friends from having fun, but a bit more spaciousness won't hurt, will it?
The discotheque can be seen as an infinite _xy_\-plane, in which there are a total of _n_ dancers. Once someone starts moving around, they will move only inside their own movement range, which is a circular area _C__i_ described by a center (_x__i_, _y__i_) and a radius _r__i_. **No two ranges' borders have more than one common point**, that is for every pair (_i_, _j_) (1 ≤ _i_ < _j_ ≤ _n_) either ranges _C__i_ and _C__j_ are disjoint, or one of them is a subset of the other. Note that it's possible that two ranges' borders share a single common point, but no two dancers have exactly the same ranges.
Tsukihi, being one of them, defines the spaciousness to be **the area covered by an odd number of movement ranges of dancers who are moving**. An example is shown below, with shaded regions representing the spaciousness if everyone moves at the same time.
<center></center>But no one keeps moving for the whole night after all, so the whole night's time is divided into two halves — before midnight and after midnight. Every dancer moves around in one half, while sitting down with friends in the other. The spaciousness of two halves are calculated separately and their sum should, of course, be as large as possible. The following figure shows an optimal solution to the example above.
<center></center>By different plans of who dances in the first half and who does in the other, different sums of spaciousness over two halves are achieved. You are to find the largest achievable value of this sum.
## Input
The first line of input contains a positive integer _n_ (1 ≤ _n_ ≤ 1 000) — the number of dancers.
The following _n_ lines each describes a dancer: the _i_\-th line among them contains three space-separated integers _x__i_, _y__i_ and _r__i_ ( - 106 ≤ _x__i_, _y__i_ ≤ 106, 1 ≤ _r__i_ ≤ 106), describing a circular movement range centered at (_x__i_, _y__i_) with radius _r__i_.
## Output
Output one decimal number — the largest achievable sum of spaciousness over two halves of the night.
The output is considered correct if it has a relative or absolute error of at most 10 - 9. Formally, let your answer be _a_, and the jury's answer be _b_. Your answer is considered correct if .
[samples]
## Note
The first sample corresponds to the illustrations in the legend.
迪斯科舞厅的拥挤从未阻止我们的朋友尽情狂欢，但再多一点空间也不会有害，对吧？
迪斯科舞厅可以看作一个无限的 #cf_span[xy]-平面，其中有总共 #cf_span[n] 位舞者。一旦有人开始移动，他们只会在其自身的移动范围内活动，该范围是一个由中心 #cf_span[(xi, yi)] 和半径 #cf_span[ri] 描述的圆形区域 #cf_span[Ci]。*任意两个范围的边界至多有一个公共点*，即对于每一对 #cf_span[(i, j)]（#cf_span[1 ≤ i < j ≤ n]），范围 #cf_span[Ci] 和 #cf_span[Cj] 要么不相交，要么其中一个完全包含于另一个。注意，两个范围的边界可能共享一个公共点，但没有两位舞者的范围完全相同。
作为其中之一的月日，将 #cf_span(class=[tex-font-style-underline], body=[spaciousness]) 定义为*被奇数个舞者移动范围覆盖的区域面积*。下图展示了一个示例，其中阴影区域表示当所有人同时移动时的 #cf_span(class=[tex-font-style-underline], body=[spaciousness])。
但毕竟没有人整夜不停移动，因此整晚被分为两个时段——午夜前和午夜后。每位舞者在其中一个时段移动，在另一个时段坐着与朋友交谈。两个时段的 #cf_span(class=[tex-font-style-underline], body=[spaciousness]) 分别计算，它们的总和当然应尽可能大。下图展示了上述示例的最优解。
通过不同的安排，决定谁在第一时段跳舞、谁在第二时段跳舞，可以获得不同的两个时段的 #cf_span(class=[tex-font-style-underline], body=[spaciousness]) 总和。你需要找出这个总和的最大可能值。
输入的第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1 000]）——舞者的数量。
接下来的 #cf_span[n] 行，每行描述一位舞者：第 #cf_span[i] 行包含三个用空格分隔的整数 #cf_span[xi]、#cf_span[yi] 和 #cf_span[ri]（#cf_span[ - 106 ≤ xi, yi ≤ 106]，#cf_span[1 ≤ ri ≤ 106]），描述以 #cf_span[(xi, yi)] 为中心、半径为 #cf_span[ri] 的圆形移动范围。
输出一个十进制数——两个时段中 #cf_span(class=[tex-font-style-underline], body=[spaciousness]) 总和的最大可能值。
当你的答案与标准答案的相对误差或绝对误差不超过 #cf_span[10 - 9] 时，视为正确。形式化地，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，你的答案正确当且仅当 。
第一个样例对应于题面中的图示。
## Input
输入的第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1 000]）——舞者的数量。接下来的 #cf_span[n] 行，每行描述一位舞者：第 #cf_span[i] 行包含三个用空格分隔的整数 #cf_span[xi]、#cf_span[yi] 和 #cf_span[ri]（#cf_span[ - 106 ≤ xi, yi ≤ 106]，#cf_span[1 ≤ ri ≤ 106]），描述以 #cf_span[(xi, yi)] 为中心、半径为 #cf_span[ri] 的圆形移动范围。
## Output
输出一个十进制数——两个时段中 #cf_span(class=[tex-font-style-underline], body=[spaciousness]) 总和的最大可能值。当你的答案与标准答案的相对误差或绝对误差不超过 #cf_span[10 - 9] 时，视为正确。形式化地，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，你的答案正确当且仅当 。
[samples]
## Note
第一个样例对应于题面中的图示。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of dancers.
For each dancer $ i \in \{1, \dots, n\} $, let $ C_i $ be a closed disk in $ \mathbb{R}^2 $ with center $ (x_i, y_i) $ and radius $ r_i $, and area $ A_i = \pi r_i^2 $.
The family $ \{C_1, \dots, C_n\} $ satisfies:
- For all $ i \ne j $, either $ C_i \cap C_j = \emptyset $, or $ C_i \subset C_j $, or $ C_j \subset C_i $.
- No two disks are identical.
Define the *spaciousness* of a subset $ S \subseteq \{1, \dots, n\} $ as the Lebesgue measure of the set of points covered by an *odd* number of disks in $ S $:
$$
\text{spaciousness}(S) = \mu\left( \left\{ p \in \mathbb{R}^2 \,\middle|\, \left| \{ i \in S \mid p \in C_i \} \right| \text{ is odd} \right\} \right)
$$
**Constraints**
1. $ 1 \le n \le 1000 $
2. $ -10^6 \le x_i, y_i \le 10^6 $, $ 1 \le r_i \le 10^6 $ for all $ i $
3. The inclusion relation among disks forms a forest (i.e., no two disks overlap partially; containment is hierarchical).
**Objective**
Partition $ \{1, \dots, n\} $ into two disjoint subsets $ S $ and $ T $ (i.e., $ S \cup T = \{1, \dots, n\} $, $ S \cap T = \emptyset $) to maximize:
$$
\text{spaciousness}(S) + \text{spaciousness}(T)
$$
API Response (JSON)
{
"problem": {
"name": "D. An overnight dance in discotheque",
"description": {
"content": "The crowdedness of the discotheque would never stop our friends from having fun, but a bit more spaciousness won't hurt, will it? The discotheque can be seen as an infinite _xy_\\-plane, in which ther",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF814D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The crowdedness of the discotheque would never stop our friends from having fun, but a bit more spaciousness won't hurt, will it?\n\nThe discotheque can be seen as an infinite _xy_\\-plane, in which ther...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "迪斯科舞厅的拥挤从未阻止我们的朋友尽情狂欢，但再多一点空间也不会有害，对吧？\n\n迪斯科舞厅可以看作一个无限的 #cf_span[xy]-平面，其中有总共 #cf_span[n] 位舞者。一旦有人开始移动，他们只会在其自身的移动范围内活动，该范围是一个由中心 #cf_span[(xi, yi)] 和半径 #cf_span[ri] 描述的圆形区域 #cf_span[Ci]。*任意两个范围的边界至多有一...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of dancers. \nFor each dancer $ i \\in \\{1, \\dots, n\\} $, let $ C_i $ be a closed disk in $ \\mathbb{R}^2 $ with center $ (x_i, y_i) $ and radi...",
"is_translate": false,
"language": "Formal"
}
]
}