A895 | Lights Out--Gold

Farmer John has installed a fancy new milking machine in his barn, but it
draws so much power that it occasionally causes the power 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 of the barn in the dark. She is curious though about
the impact of power loss on her ability to exit the barn quickly. For example,
she wonders how much farther she might need to walk 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 x-axis) and vertical (parallel
to the y-axis); the first edge can be of either type. The exit is located at
$(x_1, y_1)$. Bessie starts inside the barn located 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 any time she
reaches a vertex. Her goal is to travel a minimum distance to reach the exit.
This is relatively easy to do with the lights on, of course, since she will
travel either clockwise or counterclockwise from her current location to the
exit -- 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 possibly figure out her position by walking around and using
her sense of touch. Whenever she is standing at a vertex (including at her
initial vertex), she can feel whether it is a left turn or a right turn, and
she can tell if that vertex is the exit. When she walks along an edge of the
barn, she can determine the exact length of the edge after walking along the
entire edge. In general, Bessie will strategically feel her way around her
starting vertex until she knows enough information to determine where she is,
at which point she can easily figure out how to get to the exit by traveling a
minimum amount of remaining distance.
Please help Bessie determine the smallest possible amount by which her travel
distance will increase in the worst case (over all possibilities for her
starting vertex) for travel in the dark versus in a lit barn, assuming she
moves according to 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 of the input contains $N$ ($4 \leq N \leq 200$). Each of the
next $N$ lines contains two integers, describing the points $(x_i, y_i)$ in
clockwise order around the barn. These integers are in the range $-100,000
\ldots 100,000$.

Please output the smallest possible worst-case amount by which Bessie's
optimal distance in the dark is longer than her optimal distance in a lit
barn, where the worst case is taken over all possible vertices at which Bessie
can start.