Author: | Ihor Barenblat |
Prepared by: | Konstantinos Anemozalis |
Solved by: | |
First to solve: | UBB_Floricelele_Vesele |
Consider any two pairs of points and (C, D) where all 4 points lie on the boundary of the square. If their endpoints appear in the cyclic order A, C, B, D, we consider them to be interleaved. Any path connecting and within the square, separates from , making it impossible to connect them without forming an intersection. Thus, if an interleaved pair exists, the answer is NO.
Otherwise, it’s always possible to construct a solution. Let’s classify the pairs into three types:
Type A: Pairs with exactly one point on the boundary.
Type B: Pairs with both points on the boundary.
Type C: Pairs with neither point on the boundary.
Intuitively, since Type B pairs are not interleaved, they can be connected using curves that stay arbitrarily close to the boundary, nesting inside one another where necessary. These paths partition the square into several regions, but never in a way that separates the two endpoints of any remaining pair.
The construction is as follows:
First, connect pairs of Type A. A curve from a boundary point to an internal point does not disconnect the square, so the remaining free space stays connected; thus any two points that still need to be connected can be joined by a curve avoiding the already drawn ones.
Next, let’s consider pairs of Type B. Since they are not interleaved, we can route curves close to the boundary, going around the curves created by Type A connections and nesting around other Type B paths. Each such curve separates the square into two regions, and by the non-interleaving property, every remaining Type B pair has both endpoints in exactly one of these regions.
Finally, pairs of Type C lie entirely in the remaining connected interior. We can connect an arbitrary pair with a curve and the region remains connected, thus all such points can be joined.
A simple O(N^2) solution that checks for the interleaved condition is good enough, but the problem can also be solved in by ordering boundary points and using a stack (similarly to checking a valid parenthesis sequence).