P3134 [USACO16JAN] Lights Out G

题目描述

Farmer John 在他的谷仓里安装了一个非常不错的新挤奶机，但是这台挤奶机耗电太多了，有时候会让谷仓直接停电！这种事发生的太频繁了，以至于 Bessie 直接把谷仓的地图背过了，以便于可以在黑暗中找到谷仓的出口。她对于停电对于她快速离开谷仓的能力的影响非常好奇。比如说，她想知道她在黑暗中需要走多远来找到谷仓的出口。

谷仓里的路可以被描述为是一个简单的用几个顶点来表示的多边形，这些顶点可以按照顺时针被表示为 $(x_1, y_1) \cdots (x_n, y_n)$（保证这些顶点连成的线没有交叉的情况）。这些点构成的边在水平轴（平行于 $x$ 轴）和竖直轴（平行于 $y$ 轴）之间交替出现。第一条边可以是任意一种类型。谷仓出口在坐标 $(x_1, y_1)$ 。Bessie 从谷仓内任意一个点 $(x_i, y_i)$ 开始走。她只可以沿着这些边走，要不然是顺时针，要不然就是逆时针，她的目标就是以最短距离抵达出口。当然，如果灯亮着的话这个事还算相对简单，因为她要不然顺时针要不然逆时针走，无所谓哪个方向的路程更短一点。

一天，谷仓突然停电了，导致 Bessie 受到惊吓、忘记了她站在哪个顶点。幸亏她还记得谷仓的准确地图，所以她可以四处走走，用她的触觉来弄清楚她的位置。不管什么时候，只要她站在一个顶点，那么她就可以感受到她在这个点的朝向角度，弄清楚这个点是不是出口。当她沿着谷仓的一个边走完的时候，她可以算出精确的边长。Bessie 决定用这么一个策略：她会顺时针沿着谷仓周围的边走，直到她知道了足够的角度和边、可以推断出她目前在的是哪个顶点。在那个顶点，她就可以轻易地弄清楚怎样以最短距离到达出口（要不然继续沿着顺时针走，要不然倒回去沿着逆时针走）。

请帮助 Bessie 算出在起点可以是任何一个顶点情况下，在最坏的情况下，她在黑暗中和亮着灯的时候到达出口的距离的差值（即找到差值的最大值）。

输入格式

第一行包括一个数字 $N (4 \leqslant N \leqslant 200)$ ，接下来 $N$ 行，每行包括两个数字，沿着顺时针表示顶点 $(x_i, y_i)$，$x_i, y_i \in [-10^5, 10^5]$ 。

输出格式

输出 Bessie 在最坏的情况下，她在黑暗中和亮着灯的时候到达出口的距离的差值（即找到差值的最大值）。

输入输出样例 1

4
0 0
0 10
1 10
1 0

2

说明/提示

在这个样例中，Bessie 开始可以感觉到她沿着 $90 \degree$ 角站着，但是她辨别不出来她是在 $2, 3, 4$ 中的哪一个顶点。

在走了一条边以后，Bessie 要不然到了出口要不然就可以根据她走过的距离推断出她的位置。情况如下：

如果她从 $2$ 号点开始走，她需要在黑暗中走 $12$ 个单位，包括一个单位到达第三个点、十一个单位离开谷仓。同时，如果亮着灯，她可以只走 $10$ 个单位就离开谷仓。差值是 $2$ 。

如果从 $3$ 号点开始，她两种情况都要走 $11$ 个单位。

如果从 $4$ 号点开始，她两种情况都要走 $1$ 个单位。

所以最坏情况差值是 $2$ 。