Internet Problem Solving Contest

• Correct output – H1
• Correct output – H2
• C program solving both data sets

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₁,y₁), (x₂,y₂), ..., (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₁,y₁), (x₂,y₂), ..., (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.