Problem F: 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

C₁ with center (x₁, y₁) and radius r₁, and
C₂ with center (x₂, y₂) and radius r₂

intersect in exactly two distinct points, let

d equal the distance between the centers of C₁ and C₂,
A = atan2(y₂-y₁, x₂-x₁), and
B = acos((r₁² + d² - r₂²)/(2*r₁*d));

then the intersection points on C₁ are at angles A+B and A-B radians counterclockwise from the ray extending to the right from the center of C₁. The function atan2 is the inverse tangent function with two arguments, and acos is the inverse cosine function, both available in the math libraries of C, C++, and Java.

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 n, which is no more than 100. It is the number of blots in the dataset. Then 3n positive integers follow, with a single blank or a newline separating them.  Each group of three give the data for the circular boundary of one blot: x and y coordinate of the center of the blot and its radius, in that order. Each of these numbers will be no larger than 1,000,000. All blots lie entirely on a piece of paper, and no blot touches any edge of the paper. No two circles in a dataset will be identical. Given any two distinct circles, they will either intersect at exactly two distinct points or not intersect at all. If two circles in the input intersect, then they overlap by at least one unit. More precisely, if they have radii r₁ and r₂, where r₁ ≤ r₂, and if d is the distance between their centers, then

r₂ - r₁ + 1 ≤ d ≤ r₁ + r₂ - 1.

Three or more circles will never intersect at the same point. If C is a circle in the input that intersects at least one other input circle, and p and q are any of the intersection points of C with any of the other input circles, with p distinct from q, then p and q will be separated on C by at least 0.001 radians of arc. The restrictions on radii and angles ensure that standard double-precision arithmetic is sufficient for the calculations suggested above.

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.

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

Last modified on October 31, 2004 at 4:21 PM.