LA 3532

From Algorithmist
Jump to navigation Jump to search

LA 3532 - Nuclear Plants[edit]

Summary[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.

Explanation[edit]

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[edit]

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.

Input[edit]

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

Output[edit]

87.46
98.94