CIRU - The area of the union of circles

no tags 

You are given N circles and expected to calculate the area of the union of the circles !

Input

The first line is one integer n indicates the number of the circles. (1 <= n <= 1000)

Then follows n lines every line has three integers

Xi Yi Ri

indicates the coordinate of the center of the circle, and the radius. (|Xi|. |Yi|  <= 1000, Ri <= 1000)

Note that in this problem Ri may be 0 and it just means one point !

Output

The total area that these N circles with 3 digits after decimal point

Example

Input:
3
0 0 1
0 0 1
100 100 1


Output:
6.283

hide comments
mike_nzk: 2011-04-18 16:18:31

oh, no!!! Simpson's method is too slow and eps must be carefully selected, although I got AC at the first time.

update: However, time limit was set tighter, and I added some constant optimizations...

Last edit: 2011-02-26 12:51:38

Added by:aekdycoin
Date:2010-12-15
Time limit:0.100s-2.235s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:https://www.spoj.pl/problems/VCIRCLES/