0069. Puddles

Input file name: puddles.in
Output file name: puddles.out
Time limit: 1 s
Memory limit: 64 megabytes

Calculate the total area covered by water in n circle-formed puddles.

Input file

The first line of the input file contains number of test cases K (1≤ K≤ 10).

Each test case starts from the line containing an integer number 1≤ n≤ 100. The next n lines contain center coordinates and radii of each puddle in form xi yi ri. It is guaranteed that all numbers are integers. They do not exceed 1000 by an absolute value. Radius is always positive.

Output file

Output for each test case single real number with eight digits after decimal point – the total area covered by water.

Examples:

puddles.inpuddles.out
1 3 0 0 3 1 0 1 6 0 240.84070450


Source: Petrozavodsk Winter 2003. St. Petersburg Contest I

Discuss       Submit a solution



Printable version