Lights Out

题目描述

农夫 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 计算：在最坏情况下（对她可能的起始顶点取最坏），与灯亮时相比，她在黑暗中行走的路程会增加的最小可能值；假设在两种情况下她都按照最优策略移动。对无灯情形，“最优”策略是指使这个额外的最坏情况增量最小的策略。

输入格式

输入格式（文件 lightsout.in）： 输入第一行包含 $N$（$4 \leq N \leq 200$）。接下来 $N$ 行每行包含两个整数，按顺时针顺序描述点 $(x_i, y_i)$。这些整数在范围 $-100,000 \ldots 100,000$ 之内。

输出格式

输出格式（文件 lightsout.out）： 请输出一个数，表示在最坏情况下（对 Bessie 可能开始的所有顶点取最坏），Bessie 在黑暗中按最优策略行走的距离比在灯亮时按最优策略行走的距离多出的最小可能值。

4
0 0
0 10
1 10
1 0

2

提示

在这个例子中，Bessie 能感觉到自己起初站在一个向内的拐角处，但由于此例中所有角都是向内拐角，这几乎不给她提供信息。 一种最优策略是始终顺时针行走。如果她从顶点 3 或 4 出发，这是最优的；如果她从顶点 2 出发，则只会额外多走 2 个单位的距离。 题目鸣谢：Brian Dean

标签: USACO|2016|Platinum

来源

USACO|2016|Platinum