← All solutions

Shortest judge solution: 5282 bytes. Shortest team solution (during contest): N/A.

This geometry problem was quite painful, even compared to other painful geometry problems, and there was a lot of discussion about whether to include it or whether it was simply too hard. The algorithm is conceptually not too hard to figure out, but the implementation is a bit of a nightmare.

Let us call the two polygons P and Q. Suppose we are given an edge from P and an edge from Q that will overlap in the optimal placement (such edges always exist, unless the answer is 0, in which case we are done anyway). Let us rotate P and Q so that these two edges become horizontal with y = 0 and facing in opposite directions. Consider shifting (the rotated) P along the x-axis. The optimal placement is obtained by (at least) one such shift of P. Furthermore we may assume that in the optimal placement, either a vertex of P hits a (non-horizontal) edge of Q, a vertex of Q hits a (non-horizontal) edge of P, or a vertex of P coincides with a vertex of Q.

This means that there are only O(n²) interesting shifts of P. For each such shift, we can in O(n²) time check if the resulting polygon placements intersect, and if not, what the boundary overlap is. This polygon-polygon intersection test is already quite messy to code, but is probably something several teams have in their code library. However, this will not be fast enough: we assumed that we are given an edge from P and an edge from Q that will overlap, but we are not, which means that we have to try all n² possibilities for this as well, resulting in an Ω(n⁶) time complexity overall.

Adding several heuristics to the Ω(n⁶) was actually enough to make it run in time, but there is also a genuinely faster algorithm. The O(n⁴) time complexity for finding the best one-dimensional shift can be improved to O(n² log n) by a sweep-line style algorithm. As we shift P from −∞ to +∞, various interesting events happen:

1. A vertex of P enters or leaves the interior of Q
2. A vertex of Q enters or leaves the interior of P
3. An edge of P starts or stops crossing an edge from Q
4. Parallel edges of P and Q become overlapping

There are in total only O(n²) such events, which we can find in the same running time. We then sort the events by the x-shift at which they happen, and process them in order. At each event, we may have some obstructions causing the current shift to be invalid (because two edges cross, or a vertex is inside the other polygon, etc), or there may be no obstructions, and then we check the current overlap.

Note that when two parallel horizontal edges of P and Q overlap, their contribution to the total overlap behaves like a piecewise linear function that starts at 0, then goes up, then stays constant for a while (unless the two segments were the same length), the goes down to 0 again, and we have to keep track of the sum of these piecewise linear functions while processing the events.

Several implementation details are being swept under the rug in the above description (e.g. getting things right when a vertex of P travels along a horizontal segment of Q and vice versa), but this is the general principle. Overall one ends up with O(n⁴ log n) time (where the bottleneck is sorting the O(n²) events for each of the n² choices of overlapping edges).

One approach to make the problem more manageable is to first triangulate the polygons. This reduces the intersection tests to triangle-triangle intersection, which is much easier.

Here are some cute test case pictures: