Lattice Points in the Union of Circles

Time limit1sMemory limit128 MB

Summary

Count integer lattice points inside the union of up to 10,000 circles, restricted to the coordinate box from -16383 to 16384.

Level: Hard8 of 10
Topics: Geometry, Sorting, Brute force, Implementation
Solved: No attempts yet

Problem

You are given several circles whose center coordinates and radii are all integers. Write a program that outputs the number of points with integer coordinates that are contained in the union of these circles.

For example, in the diagram below the smaller circle (center $(1,1)$ , radius $1$ ) contains $5$ points, the larger circle (center $(2,2)$ , radius $2$ ) contains $13$ points, and the union of the two circles contains $15$ points. A point lying exactly on the boundary of a circle is considered to be contained by that circle.

As an additional constraint, the program must count only points whose $x$ and $y$ coordinates are integers in the range $-(2^{14}-1)$ to $2^{14}$ , that is, from $-16383$ to $16384$ inclusive. Circles may extend beyond this region, but points outside the region must not be counted.

Input

The input consists of several data sets. Each data set contains one line per circle. Each line holds three integers separated by spaces: the $x$ coordinate of the circle's center, the $y$ coordinate, and the radius. The end of a data set is marked by a line of three zeros, 0 0 0. A single data set contains at most 10,000 circles. A data set with no circles (that is, a 0 0 0 line appearing immediately) marks the end of the whole input.

Output

For each data set output Problem #n: followed by a single space and the answer (the number of points contained in the union). Here $n$ is the data set number, starting from $1$ .

Examples4

Example 1

Input

1 1 1
2 2 2
0 0 0
-16383 -16383 2
0 0 0
0 0 0

Expected output

Problem #1: 15
Problem #2: 6

Example 2
Input
```
0 0 1
0 0 0
0 0 0
```
Expected output
```
Problem #1: 5
```
Example 3
Input
```
0 0 2
0 0 0
0 0 0
```
Expected output
```
Problem #1: 13
```

Example 4

Input

0 0 1
0 0 0
-16383 -16383 2
16384 16384 2
0 0 0
5 5 0
0 0 0
0 0 0

Expected output

Problem #1: 5
Problem #2: 12
Problem #3: 1