ACM ICPC Asia Manila 2009: Problem G

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-e.html

( Note: Click on the figure to see a larger view. )

2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem G: ‘A eiH1 aNy 1’
Input file: g.in
Output file: stdout
Execution time limit: 30 seconds

The recent rise in the number of people contracting the flu virus had led to the study on its spread pattern. Given a population of N people in a community, there will be some people who are naturally immune from the flu virus and there are those who are not. Depending on the movement of the person, he or she also has a varying radius of transmission as represented by circles in Figure 1. However, we shall assume that each person can only be infected at center of his/her area. Figure 1 illustrates the spread of the flu virus after 4 transmissions. The first infected person is labeled with a value of 0, infecting 2, 2, 1 and 1 person, respectively, for each transmission.

(See Figure 1)

The flu virus is eventually contained at this point in time. We shall assume the center point of all people will remain the same.

Input
The input consists of multiple test cases. Each test case starts with a line containing an integer N (1 ≤ N ≤ 30) indicating the number of people in the population. Starting on the next line are 3-tuple data (x y r) representing the persons x, y coordinates and r radius of transmission. Each 3-tuple data are space delimited. Persons who are immune to the flu virus have a radius of 0. The first entry in each test case is the first person affected with the flu virus. The last test case is followed by a line containing a single zero. The coordinate system sets the origin in the top left corner of the entire area. The variables x and y are positive integers not exceeding 200. The variable r is a non-negative integer not exceeding 200.

Output

For each test case, print the case number (starting with 1) followed by the number of transmission before the flu virus is eventually contained.

Sample Input

23
50 30 20
45 20 0
70 25 0
85 30 0
10 30 0
10 40 10
25 35 0
25 20 10
35 35 10
55 35 0
65 35 20
80 40 15
105 40 10
20 55 10
40 50 10
60 50 10
85 50 10
90 55 10
110 55 5
50 65 20
70 65 5
25 70 0
95 75 0
0

Output for the Sample Input

Case 1: 4 transmissions

(Acknowledgment: This problem was contributed by Dr. Caslon Chua, De La Salle University-Manila)

.