当前没有测试数据。

Ex - 不要游泳

得分：$600$ 分

问题描述

在二维平面上，有一个凸多边形 $C$，它有 $N$ 个顶点，还有点 $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$ 的内部（除了边界）的情况下到达。

约束条件

• $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)$ 按逆时针顺序形成一个凸多边形。
• 凸多边形的任意三个点不共线。
• $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}$，则认为输出正确。

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...$。我们可以证明这是最小值。注意，你可以经过 $C$ 的边界。

注意，如果绝对或相对误差不超过 $10^{-6}$，则视为输出正确。例如，类似 5.650287 的输出也视为正确。

3
0 0
2 0
1 10
3 7
10 3

8.06225774829854965279