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
approximate 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.
You may assume all voters are unique. 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 approximate 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^{-2}$.
| 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
|
