ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Junior Contest October'2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Genie Bomber 2

Time limit: 1.0 second
Memory limit: 64 MB
Thanks to your effortful work, the genie-bomber has successfully passed all the tests. But Modest Matveevich Kamnoedov has some more problems to solve. He is concerned with efficiency of the bombing. Basically, he needs to calculate the area of a testing ground that a genie bombardment can cover.
We will assume that the testing ground is the portion of the plane defined by two inequalities: 0 ≤ x ≤ 1, 0 ≤ y ≤ 1. One genie blast zone covers a circle on the plane. Point of the testing ground is covered with the bombardment if it lies within one or more blast zones. You have to calculate the coverage efficiency – that is, the portion of the testing ground area that is covered with the bombardment.
Problem illustration

Input

In the first input line there will be one number N, which is the number of bombs dropped (N ≤ 10). The following N lines contain three numbers xi, yi, ri each, where xi and yi define the center of the ith genie bomb blast zone (0 ≤ xi, yi, ri ≤ 1), and ri defines its radius.

Output

should contain one real number - coverage efficiency percentage (that is, percentage of the testing ground area covered with the bombardment in relation to the total testing ground area, where the testing ground is the square defined by inequalities 0 ≤ x ≤ 1, 0 ≤ y ≤ 1). Precision of the result is required to be 1% or better.

Samples

inputoutput
1
0.5 0.5 0.5
78.539816
2
0.2 0.2 0.5
0.8 0.8 0.5
80.74292
Problem Author: Den Raskovalov
Problem Source: The 10th Collegiate Programming Contest of the High School Pupils of the Sverdlovsk Region (October 16, 2004)
To submit the solution for this problem go to the Problem set: 1333. Genie Bomber 2