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.
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.
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.
0.5 0.5 0.5
0.2 0.2 0.5
0.8 0.8 0.5
Problem Author: Den Raskovalov
Problem Source: The 10th Collegiate Programming Contest of the High School Pupils of the Sverdlovsk Region (October 16, 2004)