An overnight dance in discotheque
Contest: Codeforces Round 418 (Div. 2)
Difficulty rating: 2000
Tags: dfs and similar, dp, geometry, greedy, trees

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 Ci described by a center (xi, yi) and a radius ri. No two ranges' borders have more than one common point, that is for every pair (i, j) (1 ≤ i < j ≤ n) either ranges Ci and Cj 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.

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.

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 format:
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 xi, yi and ri ( - 106 ≤ xi, yi ≤ 106, 1 ≤ ri ≤ 106), describing a circular movement range centered at (xi, yi) with radius ri.

Output format:
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 $$\frac{|a-b|}{\max(1, |b|)} \leq 10^{-9}$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first sample corresponds to the illustrations in the legend.

Example input:
5
2 1 6
0 4 1
2 -1 3
1 -2 1
4 -1 1

Example output:
138.23007676

Example input:
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

Example output:
289.02652413

Editorial:
Circles' borders do not intersect, that is, each circle is "directly" contained in another circle, or is among the outermost ones. Can you see a tree/forest structure out of this?
We create a node for each of the circles Ci, with weight equal to its area π ri2. Its parent is the circle which "directly" contains it, namely the one with smallest radius among those circles containing Ci. If a circle is an outermost one, then it's made a root. This tree structure can be found in O(n2) time.
Consider what happens if there's only one group: the spaciousness equals the sum of weights of all nodes whose depths are even, minus the sum of weights of all nodes whose depths are odd.
Now we are to split the original tree/forest into two disjoint groups. This inspires us to think of a DP approach — consider a vertex u, and the parity (oddness/evenness) of number of nodes in its ancestors from the first and the second group. Under this state, let f[u][0 / 1][0 / 1] be the largest achievable answer in u's subtree.
The recursion can be done from bottom to top in O(1), and the answer we need is the sum of f[u][0][0] for all u being roots. Time complexity is O(n2) for the tree part and O(n) for the DP part. See the code for the complete recursion.
Bonus. Build the tree in $$O(n \log n)$$ time.
Bonus. Find different greedy solutions for this problem and try to prove their correctness.