問題文

二次元平面上に $N$ 頂点の凸多角形 $C$ 、点 $S=(s_x, s_y), T=(t_x,t_y)$ があります。 $C$ の頂点は、反時計回りに $(x_1,y_1),(x_2,y_2),\\ldots,(x_N,y_N)$ です。 $S,T$ は $C$ の外部にあることが保証されています。

$C$ の外周を除いた内部を通らずに点 $S$ から点 $T$ まで移動するときの最短距離を求めてください。

制約

• $3\\leq N \\leq 10^5$
• $|x_i|,|y_i|,|s_x|,|s_y|,|t_x|,|t_y|\\leq 10^9$
• $(x_1,y_1),(x_2,y_2),\\ldots,(x_N,y_N)$ は反時計回りに凸多角形をなす
• $C$ のどの $3$ 点も同一直線上にない
• $S,T$ は $C$ の外部に存在し、$C$ の外周上にない
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $y_1$ $x_2$ $y_2$ $\\vdots$ $x_N$ $y_N$ $s_x$ $s_y$ $t_x$ $t_y$

出力

答えを出力せよ。

なお、真の値との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われる。

入力例 1

4
1 1
3 1
3 3
1 3
0 2
5 2

出力例 1

5.65028153987288474496

最短距離を達成する移動方法の一例を以下の図で示します。

$(0,2) \\to (1,3) \\to(3,3)\\to(5,2)$ と移動すると、点 $S$ から点 $T$ への移動距離が $5.650281...$ となり、これが最小であることが証明できます。 $C$ の外周上は通れることに注意してください。

なお、絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われるので、5.650287 などと出力しても正解と判定されます。

入力例 2

3
0 0
2 0
1 10
3 7
10 3

出力例 2

8.06225774829854965279