Detectors

You've just escaped from your cold, dark, damp jail cell, and you still have no idea who you are or how you came to be here—but one thing you do know is that you're not out of harm's way yet. It still remains to escape from the complex. This is not easy, because even though you are gifted with the power of invisibility (being a quantum being and all) the guards have "quantum detectors" that will find you regardless. By now you have gathered that a secret, illicit organization is in operation here, which must obtain its technology from the black market. For this reason, standardization is a laughable concept, and not all of these detectors are equally sensitive—each can detect quantum beings who are less than a certain distance away, and the distance varies from detector to detector.

As you make your way across the grounds of what you now know to be the Stronghold of the Order of the Brotherhood of the Flying Hat, you notice that the boundaries of detection of the various guards' detectors often overlap, and wonder what is the total length of the "boundary"—the set of all points on the ground (making this a two-dimensional problem, thank goodness) which are not within range of any detector, but from which it is possible to end up within range of at least one detector by making an infinitesimal step towards it.

Once you have successfully escaped from the Stronghold, you realize that you somehow still remember how to code in A++, and that your Quantum Reality Protocol has a built-in A++ compiler. Before long, you have determined the answer to your question...

Problem Statement

There are n guards. Guard number i is located at coordinates (x_i,y_i) and his/her detector has a radius of r_i. Determine the total length of the boundary, as specified above.

Input Format

The first line of input will contain the integer n (0 < n ≤ 1000).

Subsequent lines will contain three real numbers: x_i, y_i, and r_i for one of the guards (-1000 ≤ x_i, y_i ≤ +1000; 0 < r_i ≤ 100)

You may assume that no two guards are standing at the same location, for that is clearly a physical impossibility.

Output Format

The total length of the boundary. Your answer must match ours with a relative or absolute error of at most 10^-6.

Sample Input

4
0 0 100
0 1 98
150 0 100
200 200 10

Sample Output

1030.375215

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 21, 2009
Author: bbi5291

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Could sample input and output be supplied please?

Done

See if you can determine, [i]for each circle[/i], how much of its circumference lies on the boundary.