Lights Out in the Barn

Farmer John installed a new milking machine in the barn. It draws so much power that the lights go out from time to time. Bessie has the map of the barn memorized, so she can still reach the exit in the dark, and she wants to know how much extra walking the darkness costs her.

The barn is a simple polygon with $N$ vertices $(x_1, y_1), \ldots, (x_N, y_N)$ at integer coordinates, listed in clockwise order. The boundary never touches or crosses itself. The edges alternate between horizontal and vertical, and the first edge can be either one. The exit is at $(x_1, y_1)$. Bessie stands at $(x_i, y_i)$ for some $i > 1$, and she knows that she is not standing at the exit.

Bessie walks only along the perimeter. She may turn around at any vertex she reaches, so she can move clockwise or counterclockwise. She knows the map, so she always knows which of the two directions along the wall is the clockwise one.

With the lights on she knows which vertex she is at, so she walks to the exit the short way around, clockwise or counterclockwise, whichever is shorter.

With the lights off she forgets which vertex she is at. She still remembers the map, and she picks up information as she moves.

• At any vertex, including the one she starts at, she feels whether the interior angle of the barn there is 90 degrees or 270 degrees.
• At any vertex she feels whether that vertex is the exit.
• After walking along a full edge she knows the exact length of that edge.

She walks until the information she has collected leaves exactly one possible starting vertex. From that moment she knows where every step took her, so she walks to the exit the short way around from where she stands. Her distance in the dark is everything she walked while identifying herself, plus that last walk.

Fix one strategy for the dark. For a starting vertex $i$, let $d_i$ be the distance that strategy makes her walk and let $s_i$ be the distance she walks with the lights on. The cost of the strategy is $\max_{i > 1} (d_i - s_i)$. Find the smallest cost over all strategies.

The first line contains $N$ ($4 \le N \le 200$).

Each of the next $N$ lines contains two integers $x_i$ and $y_i$, the vertices in clockwise order around the barn. Every coordinate is between $-100000$ and $100000$.

Print one integer, the smallest cost over all strategies for walking in the dark.