D - レースゲーム Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君は、レーシングゲームをプレイしようとしています。
レースは (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

Source Name

ARC 001