Windy Path

This problem gives us a list of arbitrary points and a list of fixed turn directions and asks if we can make a non-self-intersecting path which visits all the points while making the appropriate turn directions in the given order.

If we imagine having all left or all right turns, we see we can generate a solution by starting on the convex hull and wrapping around, removing points behind us as we go. This works because one of the properties of convex containment is that all points lie to one side of every line. If we remove points as they are used, we guarantee all remaining points are to the correct side of our post previously drawn line, and thus we "spiral" until we have finished.

How do we tackle mixing of the two?

Think of a case where each turn alternates. If we go LRLRL, then our first line we want to be on the convex hull, and when we make the left turn, we'll want to go as far left as possible, then as far right as possible, etc. We'll zig zag our way up and guarantee to cover all points. This works for a similar reason to the all the same case. When we make a turn, our PREVIOUS turn guaranteed that EVERY remaining point is in the correct direction. When we made our left hand turn, we made it as far left as possible, which guaranteed that every point was a right hand turn. Then when we made the right hand turn, we guaranteed every point would be a left hand turn.

We can combine these two cases (and the reasons they work) so a complete solution.

• start at the minimum X point
• If the next turn is L, go as far clockwise as possible.
• If the next turn is R, go as far counter clockwise as possible

We have 50 nodes, so n^2 is perfectly fine.