Problem A: Cranes
A crane is a wonderful tool for putting up a building. It makes the
job go very quickly. When the building must go up even faster, more
than one crane can be used. However, when there are too many cranes
working on the same building, it can get dangerous. As the cranes spins
around, it can bump into another crane if the operator is not careful.
Such an accident could cause the cranes to fall over, possibly causing
major damage. Therefore, safety regulations require cranes to be spaced
far enough apart so that it is impossible for any part of a crane to
touch any part of any other crane. Unfortunately, these regulations
limit the number of cranes that can be used on the construction site,
slowing down the pace of construction. Your task is to place the
cranes on the construction site while respecting the safety
regulations.
The construction site is laid out as a square grid. Several places
on the grid have been marked as possible crane locations. The arm
of each crane has a certain length r, and can rotate around
the location of the crane. The crane covers
the entire area that is no more than r units away from
the location of the crane. You are to place the cranes to maximize
the total area covered by all the cranes.
Input Specification
The first line of input contains one integer specifying the number of
test cases to follow. Each test case begins with a line containing
an integer C, the number of possible locations where a crane
could be placed. There will be no more than 15 such locations.
Each of the following C lines contains three integers
x, y, and r, all between -10 000 and 10 000 inclusive. The first two integers are the
grid coordinates of the location, and the third integer is the
length of the arm of the crane that can be placed at that location.
Sample Input
1
3
0 0 4
5 0 4
-5 0 4
Output Specification
For each test case, find the maximum area A that can be covered by
cranes, and output a line containing a single integer B
such that A = B × π .
Output for Sample Input
32
Ondřej Lhoták
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.