不要游泳

题目描述

在二维平面上,有一个具有 $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$ 在多边形外部。

求从点 $S$ 到点 $T$,除了边界以外不进入 $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}$ 时,你的输出被视为正确。

样例

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

5.65028153987288474496

一种达到最短距离的方式如下面的图所示。

如果按 $(0,2) \to (1,3) \to(3,3)\to(5,2)$ 的方式移动,从点 $S$ 到点 $T$ 的路径长度为 $5.650281\ldots$。可以证明这是最小值。注意你可以经过 $C$ 的边界。

注意,当绝对误差或相对误差不超过 $10^{-6}$ 时,你的输出被视为正确。例如,输出 5.650287 也会被视为正确。

3
0 0
2 0
1 10
3 7
10 3

8.06225774829854965279

数据范围

• $3 \le N \le 10^5$
• $|x_i|,|y_i|,|s_x|,|s_y|,|t_x|,|t_y| \le 10^9$
• $(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N)$ 按逆时针顺序构成凸多边形。
• $C$ 中任意三点不共线。
• $S$ 和 $T$ 在 $C$ 外部,且不在 $C$ 的边界上。
• 输入中的所有值均为整数。