Editorial for Baltic OI '14 P4 - Demarcation - Olympiads Online Judge

Editorial for Baltic OI '14 P4 - Demarcation

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First of all, let's introduce some operations which are used in each subtask.

$Rotate$ $R o t a t e$ - the figure is rotated $90^\circ$ $90^{\circ}$ around the axes origin. This is done by swapping $x$ $x$ and $y$ $y$ coordinates and negating the $y$ $y$ coordinate of each point.
$Move$ $M o v e$ - the figure is moved in the way that the leftmost (and lowermost if there are many) point is moved to the axes origin.
$Reflect$ $R e f l e c t$ - the figure is reflected by negating the $y$ $y$ coordinate of each point.
$Compare$ $C o m p a r e$ - checking whether two figures are congruent. This is done by $moving$ $m o v i n g$ the first figure and $rotating$ $r o t a t i n g$ , $moving$ $m o v i n g$ the second figure (four times) and each time checking if both sets of points are equal. If no, then it is tried to $reflect$ $r e f l e c t$ the second figure and run the same operations once again. If this is unsuccessful, then the figures are not congruent.

Additionally, it is needed to implement a function which cuts the figure along the given segment. The result of this function - two new figures.

The main idea - when considering two figures, they can be congruent only if they are of equal perimeters or areas. There is at most one horizontal and one vertical segment cut that gives such two figures. It can not cross any other edges of the polygon. Otherwise, there may be many segments.

Moreover, we can solve the problem by considering only the vertical cuts. We can rotate the polygon and use the same solution - the horizontal cuts will be considered too.

Subtask 1

We can see that it is possible to apply the binary search to find the $x$ $x$ coordinate of the cut. If the left perimeter is bigger than the right, we consider the left part, if the left perimeter is smaller, we consider the right part. If they are equal, we get the end points of the cut. Then we cut the figure and $compare$ $c o m p a r e$ the parts.

The complexity of this algorithm is $\mathcal O(n \cdot \log(x_{max} - x_{min}))$ $O (n \cdot \log (x_{m a x} - x_{m i n}))$ .

Subtask 2

Let's loop over all pairs of horizontal edges. In each loop, calculate the sum of lengths of edges between these edges. Get the $x$ $x$ coordinate of a cut which divides the polygon into two parts. Check whether this segment intersects other edges. If no, then make a cut and $compare$ $c o m p a r e$ the parts.

The complexity of this algorithm is $\mathcal O(n^3)$ $O (n^{3})$ .

Subtask 3

We can easily improve the algorithm which was used in the previous case by precomputing the prefix sums of lengths of edges.

Other more sophisticated algorithm uses two pointers paradigm.

Firstly, we set both pointers ( $E$ $E$ and $F$ $F$ ) to point to any horizontal edge. We keep variables $A$ $A$ and $B$ $B$ (distances between the edges pointed by $E$ $E$ and $F$ $F$ from both ends). While $edgeLength(E)+edgeLength(F) \ge A-B$ $e d g e L e n g t h (E) + e d g e L e n g t h (F) \geq A - B$ we move pointer $F$ $F$ to the next horizontal edge, otherwise we move pointer $F$ $F$ to the previous edge and $E$ $E$ to the next edge. Before moving pointers, we try to find the $x$ $x$ coordinate of a cut whose ends are on these edges and which divides the polygon into two figures of equal perimeters. Then we check whether this segment intersects other edges. If no, then make a cut and $compare$ $c o m p a r e$ the parts.

The complexity of both algorithms is $\mathcal O(n^2)$ $O (n^{2})$ .

Subtask 4

There are two main ways to implement an effective algorithm (based on equal perimeters or equal areas). We will describe the first one.

The idea is to use line sweep paradigm.

Make events for all edges which include the following information: the $x$ $x$ coordinate (the end of the horizontal edge), the $y$ $y$ coordinate of the edge, the index of the edge, and two status variables which show whether this is the left or the right end and the orientation of the edge.

Also let's keep a set with the $y$ $y$ coordinates and some additional information for all edges intersected by the cut with the given $x$ $x$ coordinate.

When processing each event we find the influenced edge in the set and the uppermost lower edge as well as the lowermost upper edge. Then we calculate the $x$ $x$ coordinates of possible segment cuts. If we find any, we insert it to the queue of events. When our $x$ $x$ sweep line hits that $x$ $x$ coordinate, we check whether the segment ends (two $y$ $y$ coordinates) are still neighbours (one immediately after another) in the set. If yes, we can perform a standard check with this segment cut. Furthermore, we are guaranteed that it won't intersect any other edges.

The complexity of this algorithm is $\mathcal O(n \log n)$ $O (n \log n)$ .

Comments

There are no comments at the moment.