Lights Out

题目描述

Farmer John 在牛棚里安装了一台很先进的新挤奶机，但它耗电量太大，以至于偶尔会导致停电！这种情况发生得非常频繁，Bessie 都把牛棚的地图背下来了，这样她在黑暗中也更容易找到出口。她很好奇停电会对她快速离开牛棚的能力造成什么影响。例如，她想知道在黑暗中为了找到出口，她可能需要多走多远。 牛棚由一个简单（不自相交）的多边形描述，其整数顶点为 $(x_1, y_1) \ldots (x_n, y_n)$，按顺时针顺序给出。它的边在水平（与 x 轴平行）和竖直（与 y 轴平行）之间交替；第一条边可以是任意一种类型。出口位于 $(x_1, y_1)$。Bessie 从牛棚内部的某个顶点 $(x_i, y_i)$ 出发，其中 $i > 1$。她只能沿着牛棚的周界行走，可以顺时针或逆时针。她的目标是以最短距离到达出口。在灯亮时这当然很容易，因为她只需从当前位置到出口，选择顺时针或逆时针中更短的方向即可。 有一天，灯熄灭了，Bessie 惊慌失措，忘记了自己站在哪个顶点上。幸运的是，她仍然记得牛棚的精确地图，所以她可以通过沿着周界走动并利用触觉来推断自己的位置。每当她站在一个顶点（包括初始顶点）时，她都能感受到该顶点精确的内角，并且能够判断该顶点是否为出口。当她沿着牛棚的一条边行走时，在走完整条边之后，她可以确定这条边的精确长度。Bessie 决定采用如下策略：她将沿着牛棚周界顺时针移动，直到她感受到了足够多的角和边，从而能够推断出自己当前所在的顶点位置。到了那时，她就可以很容易地计算出到出口的最短剩余路程：要么继续顺时针走，要么改变方向改为逆时针走。 请帮助 Bessie 确定：在最坏情况下（对所有可能的起始顶点取最坏），与在灯亮的牛棚中相比，按照黑暗中的策略她的行走距离最多会增加多少。

输入格式

第一行输入为 $N$（$4 \leq N \leq 200$）。接下来 $N$ 行每行包含两个整数，按顺时针顺序描述牛棚的点 $(x_i, y_i)$。这些整数的范围为 $-100,000 \ldots 100,000$。

输出格式

输出在题目所述策略下，从最坏起始位置出发时，Bessie 的行走距离相对于灯亮情况下增加的最大值。

4
0 0
0 10
1 10
1 0

2

提示

在这个例子中，Bessie 能感觉到自己起初站在一个 90 度角处，但她无法判断自己起初站在顶点 2、3 还是 4。 沿顺时针方向沿着一条边走一步之后，Bessie 要么到达出口，要么可以根据这条边的长度唯一确定自己的位置。她得到的距离如下： 若从顶点 2 出发：她在黑暗中行走 12 个单位（走 1 个单位到达顶点 3，然后再继续走 11 个单位到达出口）。在灯亮的牛棚中她只需要走 10 个单位。对该顶点而言，多出来的距离为 2。 若从顶点 3 出发：两种情况下她都行走 11 个单位。 若从顶点 4 出发：两种情况下她都行走 1 个单位。 因此所有起点中的最坏差值为 12 - 10 = 2。也就是说，Bessie 可以保证使用她的策略，无论从哪里开始，在黑暗中相对于有灯时最多只会多走 2 个单位距离。 题目致谢：Brian Dean

标签: USACO|2016|Gold

来源

USACO|2016|Gold