Hide

Problem J
Drawing Circles

/problems/drawingcircles/file/statement/en/img-0001.jpg
"Colorful circle pattern" Vecteezy.com
Alice likes to draw circles. Whenever she has some time, she will grab a piece of paper and draw circles on it.

Alice is drawing circles on a paper with a coordinate system. Each circle is represented by an ordered tuple $(x, y, r)$, where $(x, y)$ is the position of the circle’s center and $r$ is the radius of the circle. Since she does not like two circles to cross each other, she always erases the inside area of each new circle she draws. That is, she always erases the interior of each new circle she draws, leaving the pencil line showing the circumference. (Of course, if she overwrites an existing circle then the new pencil line simply hides the old circumference, removing it from view.)

For example (see Figure 1),

  • if she first draws $(0, 0, 1)$ and then $(0, 0, 2)$, the first circle will be completely erased; or

  • if she first draws $(-1, 0, 2)$ and then $(1, 0, 2)$, then the part of the first circle to the right of the $x = 0$ axis will be erased.

\includegraphics[width=0.8\textwidth ]{both.png}
Figure 1: Sample inputs. Dotted lines are areas that have been erased.

After drawing a number of circles, she would like to know the total length of all curved line segments that are still visible on the paper.

Input

The first line of input contains an integer $N$ $(1 \leq N \leq 2000)$ denoting the number of circles Alice drew. Each of the following $N$ lines contains three space-separated integers $x_ i$, $y_ i$, and $r_ i$ ($-10\, 000 \leq x_ i, y_ i \leq 10\, 000, 1 \leq r_ i \leq 10\, 000, i = 1 \ldots N$) describing the $i^\text {th}$ circle she drew.

Output

Output the total length of all curved line segments that are visible.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

Sample Input 1 Sample Output 1
2
0 0 1
0 0 2
12.566371
Sample Input 2 Sample Output 2
2
-1 0 2
1 0 2
20.943951

Please log in to submit a solution to this problem

Log in