D - Rail Tour
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
無限に広がる xy 平面として表現される街があります。
現在、amylase さんは点 (x_s, y_s) におり、点 (x_g, y_g) に移動したいと考えています。
この街にはただ 1 つの鉄道である陸道電鉄が存在しており、この鉄道は、n 個の点 (x_1, y_1), (x_2, y_2) ... (x_n, y_n) を順番に通る折れ線として表されます。この鉄道は途中で交差することはありません。
amylase さんは鉄道上の任意の地点で乗り降りすることができ、鉄道上では前後どちらの方向へも速度 v で移動することができます。それ以外の場所では、速度 1 で移動することができます。
amylase さんが移動に必要とする最小の時間を求めてください。
入力
入力は以下の形式で与えられる。
n v x_s y_s x_g y_g x_1 y_1 ... x_n y_n
- 1 行目には、鉄道を構成する点の数を表す整数 n (2 \leq n \leq 50)、鉄道上の移動速度を表す整数 v (2 \leq v \leq 1{,}000{,}000)、始点の座標を表す整数 x_s, y_s (-1{,}000{,}000 \leq x_s, y_s \leq 1{,}000{,}000) と、終点の座標を表す整数 x_g, y_g (-1{,}000{,}000 \leq x_g, y_g \leq 1{,}000{,}000) が与えられる。
- 続く n 行には、鉄道を構成する各点の座標が与えられる。
- x_i, y_i (-1{,}000{,}000 \leq x_i, y_i \leq 1{,}000{,}000) は、鉄道を構成する i 番目の点の座標が (x_i, y_i) であることを意味する。
- 与えられるすべての座標は整数である。
出力
始点から終点まで移動するために必要な最小の時間を 1 行で出力せよ。
絶対誤差と相対誤差のうち少なくとも片方が 10^{-6} 以下ならば正解とみなされる。
最後は改行し、余計な文字、空行を含まないこと。
入力例1
2 2 -10 0 20 0 0 0 10 0
出力例1
25
入力例2
2 2 0 3 20 3 0 0 20 0
出力例2
15.1961524227
入力例3
2 2 0 3 10 3 0 0 10 0
出力例3
10
入力例4
4 3 -10 10 10 -20 0 10 0 0 -10 -10 10 -10
出力例4
33.5702260396
入力例5
4 3 -10 10 10 -20 0 10 0 0 -50 -10 10 -10
出力例5
34.9509379141