CODE FESTIVAL 2014 Hard

D - Rail Tour


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

無限に広がる 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

Submit提出する