There are $n$ voters.
The $i$-th voter’s ideal
policy can be represented by a point in the plane $(x_i, y_i)$. Each voter has a level
of flexibility $r_i$,
representing how far a policy can be from their ideal policy
such that they are still happy, instead of unhappy. We say
those policies are in the voter’s range of
approval. Many different distance metrics may be used, but
we will use Euclidean distance here. Each voter can therefore
be represented by a disc.
These voters want to find common ground where they agree and
measure how much room there is for compromise. Determine the
exact area of the common ground.
Input
The first line contains an integer $n$, the number of voters, where
$1 \leq n \leq 500$. Then
$n$ lines follow, the
$i$-th of which containing
three integers $x_i, y_i,
r_i$, representing the $i$-th voter.
All coordinates are between $-10^4$ and $10^4$, inclusive. All radii are
between $1$ and
$2 \cdot 10^4$, inclusive.
It is guaranteed that no intersection points are distinct but
extremely close to each other, making it hard to distinguish
whether they are equal.
Output
Output the exact area of the region which represents the
common ground of the voters.
Your output is considered correct if it has at most an
absolute or relative error of $10^{-4}$.
| Sample Input 1 |
Sample Output 1 |
1
0 0 10
|
314.1592653589793116
|
| Sample Input 2 |
Sample Output 2 |
3
0 0 1
2 0 1
50 50 1000
|
0.0000000000000000
|
| Sample Input 3 |
Sample Output 3 |
3
75 83 62
6 62 78
45 89 100
|
5680.8875646107945934
|
| Sample Input 4 |
Sample Output 4 |
4
19 86 68
34 46 54
87 19 68
94 62 65
|
2102.5930287550281506
|
| Sample Input 5 |
Sample Output 5 |
5
-4 -7 90
40 30 100
3 4 54
-6 10 70
0 -20 80
|
9160.8841778678367263
|
| Sample Input 6 |
Sample Output 6 |
5
0 2 3
0 2 2
2 0 2
0 -2 2
-2 0 2
|
0.0000000000000000
|
| Sample Input 7 |
Sample Output 7 |
5
-16 63 65
-63 16 65
8 -57 65
55 -10 65
-4 3 5
|
65.3377413437073932
|
