题目描述

二次元平面上に $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$ まで移動するときの最短距離を求めてください。

输入格式

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

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

输出格式

答えを出力せよ。

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

题目大意

在二维平面上，有一个 $N$ 个顶点的凸多边形 $C$，和两个点 $S=(s_x,s_y),T=(t_x,t_y)$，$C$ 的顶点按顺时针方向依次是 $(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)$，$S$ 和 $T$ 在多边形 $C$ 的外面。

求出从 $S$ 到 $T$ 的不进入 $C$ 内部（可以与其相切）的最短路的长度。

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

5.65028153987288474496

3
0 0
2 0
1 10
3 7
10 3

8.06225774829854965279

提示

制約

• $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$ の外周上にない
• 入力は全て整数

Sample Explanation 1

最短距離を達成する移動方法の一例を以下の図で示します。  $(0,2)\ \to\ (1,3)\ \to(3,3)\to(5,2)$ と移動すると、点 $S$ から点 $T$ への移動距離が $5.650281...$ となり、これが最小であることが証明できます。 $C$ の外周上は通れることに注意してください。 なお、絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われるので、5.650287 などと出力しても正解と判定されます。