← All solutions

Shortest judge solution: 1484 bytes. Shortest team solution (during contest): 1519 bytes.

At first glance this looks like a very hard geometry problem, but a moment’s thought reveals that the problem is more combinatorial than geometric in nature. Linearizing the coordinates, we see that what we get are a bunch of intervals (on a circle) and we need to pick the smallest number of new intervals such that each input interval crosses at least one of the constructed intervals. This still looks pretty hard though, and the key observation is that the geometry of the problem actually should not be ignored completely: the fact that all wires connect two different sides of the door means that it is always possible to cut all wires using two diagonal cuts.

This means that the problem now reduces to figuring out if we can cut all wires using a single cut or not (hence the problem name). If not, using the diagonals is an optimal cut.

Checking if a single cut suffices can be done in linear time after sorting all the wire end points. We keep two pointers s and t (indicating that the cut we make is from s to t), initially pointing to the same position. Then, we repeat the following, until the s pointer has gone a whole lap around the date:

1. while we can advance t without making any wire contained within the interval (s, t), do so.
2. advance the s pointer.

(Here, “advance” means moving the pointer past the next wire end point.) During this process we keep track for each wire whether it is completely outside, partially inside, or completely inside the interval (s, t) and keep a count of how many intervals are partially inside. If at any point during the process all n wires are partially inside, we have found our single cut.

One small caveat is to make sure that the cut we make goes between two different sides of the door.