Single Cut of Failure

This problems asks us how many lines are needed to intersect all given lines on a rectangle.

The first intuition is that you can solve this with at most 2 lines by drawing them on the diagonals. Every given line must cross one of the diagonals. So now all we have to do is figure out if we can do it with one line or not. The naive way of trying all n^2 pairs of endpoints and then intersecting all n lines is obviously too slow. It's easy to optimize this by caterpillaring. Start with both ends of our candidate cut at the same place, and advance the fast pointer past each subsequent line until either we intersect all lines or doing so would cause us to NOT cut some line that we currently are. If we reach the latter case, it means the slow pointer can't possibly be an endpoint, so advance it by 1. Repeat this process until we've either found a solution or gone all the way around. This takes linear time. If we go all the way around, there is no 1 line solution and the answer is 2 lines along the diagonal.