Crop Circles
Time limit2sMemory limit512 MB
Given up to 200 unit circles centered on integer grid points, compute the area of their union, rounded to four decimals.
- Level
Medium7 of 10
- Topics
- Geometry, Math, Implementation, Sorting
- Solved
- No attempts yet
Problem
"Homer! The aliens have been at it again!" Ethel and Homer grow corn on their rectangular field. Each year, just before the harvest, part of their crop is destroyed when it is crushed (by visitors from outer space, according to Ethel) in a curious way. All corn stalks within circles of radius one meter are trampled, and the circles always lie completely within the cornfield. Homer has noticed that if he overlays the cornfield with a two-dimensional grid whose grid points are spaced precisely one meter apart in the x and y directions, then the centers of the circles occur only at the grid points. Luckily, Ethel and Homer have crop circle insurance, but to make a claim they must report the total area of destroyed crops. Note that the total area counts regions where crop circles overlap only once.
Examples (the darkened circles represent the grid points).
Total area = 5.0548
Total area = 6.8402
Input
The first line of each data set contains a single integer n, where 0 ≤ n ≤ 200, indicating the number of circles that are present. The next n lines each contain exactly two integers x and y, separated by whitespace, corresponding to the coordinates of the center of a circle. A single (x, y) pair occurs only once in this list. The end of data is indicated by a data set with n = 0.
Output
For each data set, output the total area covered by the circles in that data set, as described above. The area must be rounded to 4 decimal places. Follow the format shown in the Sample Output. Leave a blank line between output lines. Use the value 3.1415926535 to approximate π.