CF223D Spider

平面上有一个不一定是凸的、无自交的多边形，它由 $n$ 个顶点组成，顶点编号为 $1$ 到 $n$。有一只蜘蛛停在多边形的边界上，蜘蛛可以按照以下方式移动： 1. 沿边转移。蜘蛛可以从位于多边形边界上的点 $p_{1}$（坐标为 $(x_{1},y_{1})$）转移到另一个边界上的点 $p_{2}$（坐标为 $(x_{2},y_{2})$）。在转移过程中，蜘蛛不能离开多边形边界，即它的路径必须沿着多边形的边界从 $p_{1}$ 走到 $p_{2}$。蜘蛛可以自行选择沿顺时针或逆时针方向行走。 2. 垂直下降。蜘蛛可以从 $p_{1}$（坐标为 $(x_{1},y_{1})$）移动到 $p_{2}$（坐标为 $(x_{2},y_{2})$），前提是 $p_{1}$ 和 $p_{2}$ 必须在同一条竖直线上（即 $x_{1}=x_{2}$），且 $p_{1}$ 不低于 $p_{2}$（即 $y_{1} \geq y_{2}$），并且线段 $p_{1}p_{2}$ 上没有严格在多边形外部的点（特别地，该线段可以与多边形的边界有公共点）。 蜘蛛初始位于编号为 $s$ 的多边形顶点上。请你求出蜘蛛通过上述两种操作，从顶点 $s$ 移动到顶点 $t$ 的最短路径长度。距离使用普通欧氏距离度量方式。

第一行包含整数 $n$（$3 \leq n \leq 10^5$），表示多边形的顶点数。接下来 $n$ 行，每行包含两个用空格分隔的整数，表示多边形顶点的坐标。顶点按照逆时针顺序给出。每个坐标的绝对值不超过 $10^4$。 最后一行包含两个用空格分隔的整数 $s$ 和 $t$（$1 \leq s,t \leq n$），分别表示起点和终点顶点的编号。 多边形的顶点编号即为输入中给出的顺序，即第一行输入的是第一个顶点的坐标，第 $n$ 行输入的是第 $n$ 个顶点的坐标。保证所给多边形为简单多边形，即无自交和自切点。

输出一个实数，表示从顶点 $s$ 到顶点 $t$ 的最短路径长度。只要你的答案的绝对或相对误差不超过 $10^{-6}$，就被认为是正确的。

在第一个样例中，蜘蛛沿着连接顶点 $1$ 和 $4$ 的边移动。 在第二个样例中，蜘蛛无需移动，所以距离为零。 在第三个样例中，蜘蛛最优策略是从顶点 $3$ 转移到点 $(2,3)$，再下落到点 $(2,1)$，然后转移到顶点 $1$。 由 ChatGPT 5 翻译