LA 3532

From Algorithmist
Jump to navigation Jump to search

LA 3532 - Nuclear Plants[edit]


Given is a grid and a set of small circles with centers in some of the grid points. (The radius of each circle is either 0.58 or 1.31, where 1 is the distance of two neighboring grid points.) The grid is fairly large, the number of circles is fairly small.]

Compute the area of the part of the grid not covered by any circle.


Most of the unit squares are empty. The interesting ones only occur near the circle centers. For these some numerical approach can be used. (For example, if a square intersects more than one circle, split it into four smaller squares, otherwise determine the exact answer.)

For added precision and speed, the "type" of a unit square only depends on the types of circles in several grid points nearby. The area of each "type" of a unit square can be precomputed.


In C++, you can first use a set< pair<int,int> ></syntaxhighlight> to store the coordinates of all interesting squares, then process these squares one by one.


10 10 2 2
2 2
4 4
5 6
1 8
10 10 1 0
5 5
0 0 0 0