← 返回题目列表

Codeforces · 223/D

D. 蜘蛛

中文机器翻译题面 查看原题

平面包含一个没有自交的不一定是凸多边形,由 n 个顶点组成,编号从 1 到 n。有一只蜘蛛坐在多边形的边界上,蜘蛛可以这样移动:

1. 转移。蜘蛛从位于多边形边界上、坐标为 (x1, y1) 的点 p1 移动到同样位于边界上、坐标为 (x2, y2) 的点 p2。蜘蛛在移动时不能超出多边形边界,即蜘蛛从点 p1 到点 p2 的路径沿着多边形边界。由蜘蛛选择绕多边形边界行走的方向(顺时针或逆时针)。
2. 下降。蜘蛛从坐标为(x1, y1)的点p1移动到坐标为(x2, y2)的点p2,此时点p1和p2必须位于一条垂直直线上(x1 = x2),点p1必须不低于点p2(y1 ≥ y2)并且线段p1p2不能有严格位于多边形外部的点(具体来说,线段可以有公共点)与边框)。

最初,蜘蛛位于编号为 s 的多边形顶点。求到顶点编号 t 的最短路径的长度,包括转移和下降。距离由通常的欧几里得度量 $$| 确定。 p_{1}p_{2}| = \sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}$$。

输入

第一行包含整数 n (3 ≤ n ≤ 105) — 给定多边形的顶点数。接下来的 n 行每行包含两个空格分隔的整数 - 多边形顶点的坐标。顶点按逆时针顺序列出。多边形顶点坐标的绝对值不超过104。

最后一行包含两个空格分隔的整数 s 和 t (1 ≤ s, t ≤ n) — 所寻找的最短路径的起始和结束顶点。

考虑按输入中给出的顺序编号的多边形顶点,即第一个顶点的坐标位于输入的第二行,第 n 个顶点的坐标位于第 (n + 1) 行。保证给定的多边形是简单的,即它不包含自交或自相切。

输出

在输出中打印一个实数——从顶点 s 到顶点 t 的最短路径的长度。如果答案的绝对误差或相对误差不超过 10 - 6,则认为答案是正确的。

示例

输入 #1

4
0 0
1 0
1 1
0 1
1 4

输出 #1

1.000000000000000000e+000

输入 #2

4
0 0
1 1
0 2
-1 1
3 3

输出 #2

0.000000000000000000e+000

输入 #3

5
0 0
5 0
1 4
0 2
2 1
3 1

输出 #3

5.650281539872884700e+000

注意

在第一个示例中,蜘蛛沿着连接顶点 1 和 4 的边移动。

在第二个示例中,蜘蛛不必转移到任何地方,因此距离为零。

在第三个示例中,蜘蛛的最佳策略是从顶点 3 转移到点 (2,3),下降到点 (2,1),然后转移到顶点 1。