# LA 3532

Jump to navigation Jump to search

## 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. 

Input10 10 2 2 2 2 4 4 5 6 1 8 10 10 1 0 5 5 0 0 0 0 Output87.46 98.94