## IPSC 2004

## Solution to Problem H – Hard Question – P=NP?

First of all, if any of the edges of the National Park is not
axis-parallel, then the National Park cannot be a union of axis-parallel
rectangles. Furthermore, every rectangular plot which does not lie entirely
in the National Park can be safely discarded. To compute whether
a rectangle plot lies entirely inside the Nationl Park, it suffices to
check if none of its sides intersects any edge of the National Park,
and check if some interior point of the plot (say the center) lies
inside the Park. What remains is a set of plots which lie completely
inside the National Park. Since the plots are mutually disjoint, the
plots cover the National Park if and only if the area of the National Park
and the sum of the areas of the plots are equal. The time complexity of
this algorithm is **O(MN)**.

### Implementation details

To compute the area of a polygon **(x**_{1},y_{1}),
(x_{2},y_{2}), ..., (x_{N}, y_{N})
we use the known equation **area = ∑
(x**_{i}-x_{i+1})*(y_{i+1}+y_{i})/2,
where we sum for **i=1,2,...,N** and the **(N+1)**-st vertex
equals to the first one.

The easiest way to determine whether a point **A** lies inside the
polygon **(x**_{1},y_{1}),
(x_{2},y_{2}), ..., (x_{N}, y_{N})
is to find the sum of oriented angles **∑
(x**_{i},y_{i})A(x_{i+1},
y_{i+1}). If **A** lies inside the polygon the sum is
**± 2Π**. (The sign depends on the orientation of the
polygon.) Otherwise, the sum is zero.

All other computations are trivial.