LA 3532

Summary

Given is a $N\times M$ 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.

Explanation

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.

Implementations

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

87.46
98.94