102867: [AtCoder]ABC286 Ex - Don't Swim

Problem Statement

On a two-dimensional plane, there is a convex polygon $C$ with $N$ vertices, and points $S=(s_x, s_y)$ and $T=(t_x,t_y)$. The vertices of $C$ are $(x_1,y_1),(x_2,y_2),\ldots$, and $(x_N,y_N)$ in counterclockwise order. It is guaranteed that $S$ and $T$ are outside the polygon.

Find the shortest distance that needs to be traveled to get from point $S$ to point $T$ without entering the interior of $C$ except for its circumference.

Constraints

• $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$, and $(x_N,y_N)$ form a convex polygon in counterclockwise order.
• No three points of $C$ are colinear.
• $S$ and $T$ are outside $C$ and not on the circumference of $C$.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Your output is considered correct if the absolute or relative error from the true value is at most $10^{-6}$.

Sample Input 1

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

Sample Output 1

5.65028153987288474496

One way to achieve the shortest distance is shown in the following figure.

If you travel as $(0,2) \to (1,3) \to(3,3)\to(5,2)$, the length of the path from point $S$ to point $T$ is $5.650281...$. We can prove that it is the minimum. Note that you may enter the circumference of $C$.

Note that your output is considered correct if the absolute or relative error is at most $10^{-6}$. For example, output like 5.650287 is also considered correct.

Sample Input 2

3
0 0
2 0
1 10
3 7
10 3

Sample Output 2

8.06225774829854965279

问题描述

在一个二维平面上，有一个具有$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$的最短距离，除了多边形的边界外，不能进入多边形的内部。

限制条件

• $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...$。我们可以证明这是最小的。请注意，你可能需要进入$C$的边界。

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

样例输入2

3
0 0
2 0
1 10
3 7
10 3

样例输出2

8.06225774829854965279