Lights Out (Platinum)#10603
Farmer John has installed a fancy new milking machine in his barn, but it draws so much power that it occasionally causes the electricity to go out! This happens so often that Bessie has memorized a map of the barn, making it easier for her to find the exit in the dark. She is curious, however, about how power outages affect her ability to exit the barn quickly. For example, she wonders how much farther she might need to walk to find the exit in the dark.
The barn is described by a simple (non-self-intersecting) polygon with integer vertices (x_1, y_1), \ldots, (x_n, y_n) listed in clockwise order. Its edges alternate between horizontal (parallel to the -axis) and vertical (parallel to the -axis); the first edge can be of either type. The exit is located at (x_1, y_1). Bessie starts inside the barn at some vertex (x_i, y_i) for i > 1. She can walk only around the perimeter of the barn, either clockwise or counterclockwise, potentially changing direction whenever she reaches a vertex. Her goal is to travel the minimum possible distance to reach the exit. This is relatively easy to do with the lights on, of course, since she can travel either clockwise or counterclockwise from her current location to the exit, choosing whichever direction is shorter.
One day, the lights go out, causing Bessie to panic and forget which vertex she is standing at. Fortunately, she still remembers the exact map of the barn, so she can potentially determine her position by walking around and using her sense of touch. Whenever she is standing at a vertex (including her initial vertex), she can feel whether it is a left turn or a right turn, and she can tell whether that vertex is the exit. When she walks along an edge of the barn, she can determine its exact length after traversing the entire edge.
In general, Bessie will strategically feel her way around her starting vertex until she has enough information to determine where she is. At that point, she can easily determine the shortest way to reach the exit by traveling the minimum possible remaining distance.
Please help Bessie determine the smallest possible amount by which her travel distance will increase in the worst case (over all possible starting vertices) when traveling in the dark compared to traveling in a lit barn, assuming she uses an optimal strategy in each case. An "optimal" strategy for the unlit case is one that minimizes this extra worst-case amount.
The first line contains an integer n~(4 \le n \le 200). Each of the next lines contains two integers, describing the points (x_i, y_i) in clockwise order around the barn. These integers are in the range -10^5 to 10^5.
Print the smallest possible worst-case amount by which Bessie's optimal travel distance in the dark exceeds her optimal travel distance in a lit barn, where the worst case is taken over all possible vertices at which Bessie can start.
In this example, Bessie can determine that she is initially standing at an inward bend. However, since all corners in this example are inward bends, this gives her little information.
One optimal strategy is to simply travel clockwise. This is optimal if she starts at vertex or , and it adds only units of distance if she starts at vertex .
Example 1