Editorial for ICPC PACNW 2016 L - Windy Path
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
We'll show a solution always exists by constructing one. Let's start on a point on the convex hull of all the points. We'll maintain the invariant that we are always on a point on the convex hull of the remaining points.
Now, if our next turn needs to be left (resp right), we'll choose the rightmost point (resp leftmost) of the remaining points. This takes care of turns, so we just need to verify that the path doesn't intersect itself.
This next point is guaranteed to be on the convex hull. So, this is a segment connecting two points on the convex hull, so it is impossible for any future segment to intersect this one.
Thus, this greedy algorithm works for all cases.
Comments