問題文
比赛是 从 (x, y) = (start, 0) 开始, 我会朝着(x, y) = (goal, N) 的目标奔跑。 对于
0 ≦ k ≦ N 的 y=k ,给出了路线存在的左端和右端,并且依次连接每个端的线的内侧是路线。

图:输入1的示例。红色圆圈是起点。蓝色圆圈是目标。棕色部分是课程。
比赛中使用的车辆不能在赛道以外的任何地方行驶。还假设车辆可以瞬间改变方向,并且车辆的宽度和长度可以忽略不计。
高桥先生想要找到从起点到终点的最短路线,以征服这款赛车游戏。
入力
N start goal l_0 r_0 l_1 r_1 : : l_N r_N
- 1 行显示花边的总长度。 N 给出。
- 2 行显示课程的起点。 start 坐标和目标点 goal 坐标以空格分隔。
- 继续 3 在 N+2 在每一行中, 上线i+3 在行中y=i 当然是左端 l_i 和课程的右端 r_i 作为空格分隔符给出。
- 此外,每个输入值满足以下条件。
- N 是一个整数并且1 ≦ N ≦ 200,000 满意。
- l_i 和 r_i 是一个整数并且0 ≦ l_i < r_i ≦ 1,000,000 满意。
- start 是一个整数并且l_0 ≦ start ≦ r_0 满意。
- goal 是一个整数并且l_N ≦ goal ≦ r_N 满意。
出力
输出是绝对误差或相对误差。 1e-9 允许以下内容。
入力例 1
7 3 3 2 5 4 6 2 3 3 6 3 4 4 6 2 5 1 5
出力例 1
8.22677276241436
- 以红色圆圈为起点,蓝色圆圈为目标,下图中的红线路线是最短的。

入力例 2
5 3 3 0 5 0 5 0 5 0 5 0 5 0 5
出力例 2
5