P6176 [USACO16JAN] Lights Out P

题目描述

农夫约翰在他的谷仓里安装了一台新的挤奶机，但它耗电量太大，偶尔会导致停电！这种情况发生得如此频繁，以至于贝茜已经记住了谷仓的地图，这帮助她在黑暗中更容易找到出口。但她好奇停电会对她快速离开谷仓的能力产生多大影响。例如，她想知道在黑暗中寻找出口可能需要多走多少路。

谷仓由一个简单（无自交）多边形描述，其顶点按顺时针顺序排列为 $(x_1,y_1)\ldots(x_n,y_n)$。多边形的边在水平（平行于 $x$ 轴）和垂直（平行于 $y$ 轴）之间交替；第一条边可以是任意类型。出口位于 $(x_1,y_1)$。贝茜从某个顶点 $(x_i,y_i)$（$i > 1$）开始位于谷仓内部。她只能沿着谷仓的周边行走，可以顺时针或逆时针方向移动，并可在到达顶点时随时改变方向。她的目标是以最短距离到达出口。在有灯光的情况下这很容易，因为她只需从当前位置沿顺时针或逆时针中选择较短的方向行进即可。

某天停电时，贝茜因恐慌而忘记了自己所在的起始顶点。幸运的是，她仍清楚记得谷仓的地图，因此她可能通过行走并利用触觉来确定自己的位置。每当她站在一个顶点时（包括初始顶点），她可以感知该顶点是左转还是右转，并能判断该顶点是否是出口。当她沿着谷仓的边行走时，她可以在走完整条边后确定该边的精确长度。贝茜将策略性地探索周围环境，直到获得足够信息来确定自己的位置，之后她就能轻松计算出剩余的最短路径。

请帮助贝茜计算：在最优策略下，黑暗中最坏情况（考虑所有可能的起始顶点）下她的行走距离相比有灯光时可能增加的最小额外距离。这里的“最优策略”指能最小化这种最坏情况额外距离的策略。

输入格式

输入第一行包含 $N$（$4 \leq N \leq 200$）。接下来 $N$ 行每行包含两个整数，按顺时针顺序描述多边形顶点 $(x_i,y_i)$。这些整数的范围在 $-100,000$ 到 $100,000$ 之间。

输出格式

请输出在最优策略下，贝茜在黑暗中最坏情况（考虑所有可能的起始顶点）下的行走距离相比有灯光时可能增加的最小额外距离。

输入输出样例 1

4
0 0
0 10
1 10
1 0

2

说明/提示

在此示例中，贝茜可以感知到自己初始位于一个内角处，但由于所有角都是内角，这提供的信息有限。

一种最优策略是始终顺时针行走。如果她从顶点 3 或 4 出发，这是最优选择；如果从顶点 2 出发，则只会增加 2 单位距离。