Dark Barn Navigation

Farmer John’s barn is modeled as a simple (non self‐intersecting) polygon with n vertices given in clockwise order. The polygon’s edges alternate between horizontal and vertical segments. The exit is located at vertex \( (x_1,y_1) \). Bessie starts at some other vertex \( (x_i,y_i) \) for \( i > 1 \) and wishes to reach the exit by walking along the perimeter. With the lights on, she can easily choose the shorter of the two paths (clockwise or counterclockwise) along the perimeter. Her minimum travel distance is given by

\[ OPT(i)=\min\left( d_{cw}(i,1),\; d_{ccw}(i,1)\right), \]

where \( d_{cw}(i,1) \) denotes the distance traveling clockwise from vertex \( i \) to vertex \( 1 \), and \( d_{ccw}(i,1) \) is the counterclockwise distance.

When the barn goes dark, Bessie forgets where she is. However, she still remembers the barn’s exact map. At any vertex she can feel if it is a left turn or a right turn (determined by the sign of the cross product between the incoming and outgoing edges) and whether that vertex is the exit. While walking along an edge she also learns its length. Using these clues, Bessie can eventually deduce her starting vertex – but she may have to walk farther than in the lit case.

More precisely, assume that Bessie adopts the following strategy in the dark: starting from her unknown vertex \( i \), she always walks clockwise along the barn perimeter, recording, at each vertex, the edge length she just traversed and the turn type (left/right) at the new vertex. Initially, her candidate set consists of all vertices (other than the exit) whose turn type (felt at the vertex) matches what she experiences at her starting vertex. As she walks, she simultaneously compares her observations with what she would have sensed had she started from any candidate vertex. She eliminates any candidate whose expected sequence (of edge lengths and turns) does not match the observed sequence. Once her candidate set is reduced to a single vertex (or she reaches the exit), she deduces her current location and then proceeds optimally (i.e. via the minimum remaining distance along the perimeter) to the exit.

Your task is to help Bessie determine the smallest possible worst‐case extra distance she must travel in the dark compared to the distance she would have traveled with the lights on. Formally, if for a starting vertex \( i \) the distance Bessie travels in the dark (using an optimal strategy) is \( D(i) \) and the lit distance is \( OPT(i) \), compute

\[ \max_{i>1} \Bigl(D(i)-OPT(i)\Bigr). \]

Input format note: The barn is given by n vertices with integer coordinates \( (x_1,y_1),\ (x_2,y_2),\dots, (x_n,y_n) \) listed in clockwise order. The exit is at vertex 1. It is guaranteed that the edges alternate between horizontal and vertical.

inputFormat

The first line contains a single integer \( n \) (with \( n\ge3 \)). The next \( n \) lines each contain two integers \( x_i \) and \( y_i \) describing the coordinates of the \( i^{th} \) vertex of the barn in clockwise order. Vertex 1 is the exit. All coordinates are integers.

outputFormat

Output a single integer: the smallest possible worst‐case extra distance (over all possible starting vertices with \( i>1 \)) that Bessie will travel in the dark compared to the lit barn scenario.

sample

4
0 0
1 0
1 1
0 1

2