← 返回题目列表

AtCoder · arc001_4

D. 赛车游戏

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

問題文

高桥正在尝试玩赛车游戏。
比赛是 从 (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 满意。

出力

比赛的最短路线 1 按行输出。
输出是绝对误差或相对误差。 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