赛车游戏AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)高橋君は、レーシングゲームをプレイしようとしています。 レースは $(x, y) = (start, 0)$ からスタートし、$(x, y) = (goal, N)$ のゴールに向かって走っていきます。 $0 ≦ k ≦ N$ の $y=k$ に対してコースの存在する左端と右端が与えられ、それぞれを順に結んだ線の内側がコースとなります。 
図：入力1の例。赤丸がスタート地点。青丸がゴール地点。茶色部分がコースとなる。 レースに使う車はコース上以外を走ることは出来ません。また、一瞬で方向転換できるものとし、車の幅及び長さは無視できるものとします。 高橋君は、このレーシングゲームを攻略するためにスタートからゴールまでの最短経路を求めたいです。
高桥君准备玩一款赛车游戏。比赛从 $(x, y) = (start, 0)$ 出发，向 $(x, y) = (goal, N)$ 的终点行驶。对于 $0 ≦ k ≦ N$ 的 $y=k$，给出了赛道存在的最左端和最右端，依次连接这些端点后，两条线所围成的内部区域就是赛道。 图：输入 1 的示例。红色圆点为起点，蓝色圆点为终点，棕色部分为赛道。
比赛使用的车辆不能驶出赛道。车辆可以瞬间改变方向，并且可以忽略车辆的宽度和长度。高桥君希望求出从起点到终点的最短路径，以攻略这款赛车游戏。
AI (CI翻译)
Input
输入格式
AI (CI翻译)入力は以下の形式で与えられる。 $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$ を満たす。
输入格式如下：
$N$ $start$ $goal$ $l_0$ $r_0$ $l_1$ $r_1$ $:$ $:$ $l_N$ $r_N$
第 $1$ 行给出比赛的总长度 $N$。
第 $2$ 行以空格分隔给出赛道起点的 $start$ 坐标和终点的 $goal$ 坐标。
从第 $3$ 行到第 $N+2$ 行，每行以空格分隔给出 $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$。AI (CI翻译)
Output
输出格式
AI (CI翻译)レースの最短経路を $1$ 行で出力せよ。 なお、出力は絶対誤差または相対誤差 $1e-9$ 以下までを許容する。
在一行中输出比赛的最短路径长度。允许绝对误差或相对误差不超过 $1e-9$。AI (CI翻译)
AI (CI翻译)
样例
7
3 3
2 5
4 6
2 3
3 6
3 4
4 6
2 5
1 5
8.22677276241436
5
3 3
0 5
0 5
0 5
0 5
0 5
0 5
5
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。