题目描述

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 \gt 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.

题目大意

题目大意：

按顺时针顺序给你$N$ $(4≤N≤200)$ 点，围成一个N边形农场。贝西要从某一点p出发走道农场1，她不知道自己在哪个点。

她先按顺时针顺序走若干个点，记录下她所走的每条边的长度和每次转弯的角度，如果从当前记录的信息能够准确判断她所在的位置，她就可以选择继续以往前走或掉头往回走两种方式中距离较短的方式来走到1。

现求对于所有不同的出发点，从原位置直接走到1的较短路径（顺或逆时针走）和贝西以上述的这种方式走出的路径长度的差值的最大值。

备注：所给农场所有的边均水平或竖直，记录“转弯的角度”可以理解为记录转了90°或270°，即顺时针转弯或逆时针转弯。

输入数据给出$N$和$N$个横坐标和纵坐标的绝对值都不超过$10^5$的点，按照题目要求输出。

4
0 0
0 10
1 10
1 0

2

提示

In this example, Bessie can feel that she is initially standing at an inward bend, however since in this example all corners are inward bends this tells her little information.

One optimal strategy is to just travel clockwise. This is optimal is she starts at vertex 3 or 4 and only adds 2 units of distance if she starts at vertex 2.