Problem D
Ink Blots
|
|
|
Figure 1: 1 White Region |
Figure 2: 3 White Regions |
Figure 3: 4 White Regions |
Drops of dark ink can fall on a white piece of paper creating a number of round ink blots. Three examples are shown above. The blots can create multiple distinct white regions. In the first figure, there is just one white region. In the second figure there is the outer white region plus a small white region bounded by the left four blots and an even smaller white region bounded by the right three blots. In the third figure, there are four white regions, one on the very outside, one inside the outer ring of blots and outside the four blots in the middle, and two tiny ones each formed between three of the four inner blots.
Two points are in the same white region if a path can be drawn between them that only passes through white points. Your problem is to count the number of white regions given the centers and radii of the blots.
Math Formulas: If circles
with center and radius , and
with center and radius
intersect in exactly two distinct points, let
equal the distance between the centers of and ,
, and
then the intersection points on
Input
There are from one to 15 data sets, followed by a final line
containing only 0. A data set starts with a line containing a
single positive integer
Three or more circles will never intersect at the same
point. If
The sample input below corresponds to the figures above, though the scale is different in each figure.
Output
The output contains one line for each data set. The line contains only the number of white regions for the dataset, which is never more than 200.
Warning
Brute force raster methods of solving this problem will take up too much memory and be too slow.
Sample Input 1 | Sample Output 1 |
---|---|
4 45 45 40 65 55 35 45 45 10 20 95 10 5 30 30 20 30 60 20 60 30 20 60 60 20 90 45 15 16 200 120 65 300 100 55 400 120 65 480 200 65 500 300 55 480 400 65 400 480 65 300 500 55 200 480 65 120 400 65 100 300 55 120 200 65 300 245 60 300 355 60 385 300 51 215 300 51 0 |
1 3 4 |