问题描述

在一个二维平面上，有一个凸多边形$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)$ 按逆时针顺序组成一个凸多边形。
• $C$ 的任意三个顶点不共线。
• $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...$。我们可以证明这是最小值。请注意，你可能会进入多边形的圆周。

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

示例输入 2

3
0 0
2 0
1 10
3 7
10 3

示例输出 2

8.06225774829854965279