Lights Out (Gold)#10600
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), and the first edge can be of either type. The exit is located at (x_1, y_1). Bessie starts inside the barn at a vertex (x_i, y_i) for i > 1. She can walk only along the perimeter of the barn, either clockwise or counterclockwise. 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 the exact interior angle at that vertex, and she can tell whether that vertex is the exit. When she walks along an edge of the barn, she can determine the exact length of the edge after traversing the entire edge.
Bessie decides on the following strategy: she will move clockwise around the perimeter of the barn until she has felt enough angles and edges to determine the vertex at which she is currently located. At that point, she can easily determine the shortest way to reach the exit, either by continuing clockwise or by switching directions and moving counterclockwise.
Please help Bessie determine the largest 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.
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 \le x_i, y_i \le 10^5.
Output the largest amount by which Bessie's travel distance increases in the worst case over all possible starting vertices when using the strategy described above.
In this example, Bessie can determine that she is initially standing at a -degree angle, but she cannot tell whether she is initially standing at vertex , or . After taking a step along one edge in the clockwise direction, she either reaches the exit or can uniquely determine her location based on the length of this edge. The distances she travels are as follows:
If starting at vertex , she travels units in the dark: unit to reach vertex , followed by units to continue to the exit. In a lit barn, she only needs to travel units. Thus, she travels an extra units for this starting vertex.
If starting at vertex , she travels units in both cases.
If starting at vertex , she travels unit in both cases.
Therefore, the worst-case difference over all possible starting vertices is 12 - 10 = 2. In other words, Bessie can guarantee that, regardless of where she starts, she will travel at most extra units in the dark compared to the light using her strategy.
Example 1