CF223D.Spider

A plane contains a not necessarily convex polygon without self-intersections, consisting of n vertexes, numbered from 1 to n. There is a spider sitting on the border of the polygon, the spider can move like that:

1. Transfer. The spider moves from the point _p_1 with coordinates (_x_1, _y_1), lying on the polygon border, to the point _p_2 with coordinates (_x_2, _y_2), also lying on the border. The spider can't go beyond the polygon border as it transfers, that is, the spider's path from point _p_1 to point _p_2 goes along the polygon border. It's up to the spider to choose the direction of walking round the polygon border (clockwise or counterclockwise).
2. Descend. The spider moves from point _p_1 with coordinates (_x_1, _y_1) to point _p_2 with coordinates (_x_2, _y_2), at that points _p_1 and _p_2 must lie on one vertical straight line (_x_1 = _x_2), point _p_1 must be not lower than point _p_2 (_y_1 ≥ _y_2) and segment _p_1_p_2 mustn't have points, located strictly outside the polygon (specifically, the segment can have common points with the border).

Initially the spider is located at the polygon vertex with number s. Find the length of the shortest path to the vertex number t, consisting of transfers and descends. The distance is determined by the usual Euclidean metric .

一个平面内包含一个未必是凸的、无自交的多边形，该多边形有 $n$ 个顶点，编号从 $1$ 到 $n$。一只蜘蛛位于该多边形的边界上，它可以按如下方式移动：

1. 转移：蜘蛛从边界上一点 $p_1$（坐标为 $(x_1,\,y_1)$）移动到边界上另一点 $p_2$（坐标为 $(x_2,\,y_2)$）。转移过程中，蜘蛛不得越过边界，即其路径必须严格沿多边形边界进行；蜘蛛可自主选择绕行方向（顺时针或逆时针）。

2. 下降：蜘蛛从点 $p_1$（坐标为 $(x_1,\,y_1)$）移动到点 $p_2$（坐标为 $(x_2,\,y_2)$），要求两点位于同一竖直直线（即 $x_1 = x_2$），且 $p_1$ 不低于 $p_2$（即 $y_1 \ge y_2$），同时线段 $p_1p_2$ 不得包含严格位于多边形外部的点（即该线段可与边界有公共点，但不可穿出多边形内部）。

初始时，蜘蛛位于编号为 $s$ 的多边形顶点。求从顶点 $s$ 到顶点 $t$ 的最短路径长度（路径由若干次“转移”和“下降”组成）。距离按通常的欧几里得度量计算：

The first line contains integer n (3 ≤ n ≤ 105) — the number of vertexes of the given polygon. Next n lines contain two space-separated integers each — the coordinates of the polygon vertexes. The vertexes are listed in the counter-clockwise order. The coordinates of the polygon vertexes do not exceed 104 in their absolute value.

The last line contains two space-separated integers s and t (1 ≤ s, t ≤ n) — the start and the end vertexes of the sought shortest way.

Consider the polygon vertexes numbered in the order they are given in the input, that is, the coordinates of the first vertex are located on the second line of the input and the coordinates of the n-th vertex are on the (n + 1)-th line. It is guaranteed that the given polygon is simple, that is, it contains no self-intersections or self-tangencies.

第一行包含一个整数 $n$（$3 \leq n \leq 10^5$）—— 给定多边形的顶点数。接下来的 $n$ 行每行包含两个以空格分隔的整数 —— 多边形各顶点的坐标。顶点按逆时针顺序给出。多边形顶点坐标的绝对值不超过 $10^4$。

最后一行包含两个以空格分隔的整数 $s$ 和 $t$（$1 \leq s, t \leq n$）—— 所求最短路径的起点和终点顶点编号。

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

In the output print a single real number — the length of the shortest way from vertex s to vertex t. The answer is considered correct, if its absolute or relative error does not exceed 10 - 6.

在输出中打印一个实数——从顶点 $s$ 到顶点 $t$ 的最短路径长度。若答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

In the first sample the spider transfers along the side that connects vertexes 1 and 4.

In the second sample the spider doesn't have to transfer anywhere, so the distance equals zero.

In the third sample the best strategy for the spider is to transfer from vertex 3 to point (2,3), descend to point (2,1), and then transfer to vertex 1.

在第一个样例中，蜘蛛沿着连接顶点 1 和顶点 4 的棱爬行。

在第二个样例中，蜘蛛无需转移，因此距离为零。

在第三个样例中，蜘蛛的最优策略是：从顶点 3 转移到点 $(2,3)$，再下降到点 $(2,1)$，最后转移到顶点 1。