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 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.
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
0 0 10 314.159
0 0 10
0 10 10 505.482