Algorithm Problem 1 : Med

This problem I got to solve on “Prodyogiki 09” in an University Competition of NITs. I was unable to solve that. Try to solve this.

Problem Level: Med

Problem statement: The world is at war. The machine have vowed to clear the human race and the human have determined to make machine extinct. You have been elected as leader of resistance. You need to destroy the Cyberdyne systems. In a bid to do so, u have launched an air attack on Cyberdine. This tasks is, like so many things, best accomplished by randomly blowing things up. Fortunately, you have a proven talent in this area.

Even as we speak, your warplanes are dropping large bombs all over the machines. You need some way to determine  the extent of  the  carnage.  If  the pilots have  served you well,  they may  live  for  another precious day. You don’t really care about the property damage or the massive casualties. As such, all you want to know is the total area of devastation. Every bomb has a destruction radius. Anything within that radius  is completely eradicated. Computing the area for one bomb  is fairly simple, but for many  it  isn’t quite so easy. However, your human friends have surprisingly  large proportion of skilled programmers, so  you  have  respectfully  requested  their  assistance.  The  survivors  of  this  request  (ie,  those  who cooperated) are now hard at work, writing a program to solve this problem…

Input 

Input consists of a number of cases. Each case lists all of the bombs dropped on one day of your rule. The first line of case contains n, the number of bombs. The next n lines each contain the x and y coordinates where one bomb exploded, and its destruction radius. There will be at most 100 bombs. Coordinates given are real numbers between 0 and 100, and the radius is a real number between 0 and 10.

There will be at most 50 cases. The last day of bombing will be followed by a line containing 0. This case must not be processed.

Output 

For each case, output the area of destruction from all of the bombs from that day, accurate to three decimal places.

Sample Input Output for Sample Input 

1
0 0 10                     314.159

2
0 0 10
0 10 10                    505.482