Score : $600$ points

问题描述

在一个二维平面上，存在一个有 $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$ 的边界外，不能进入其内部。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:59:03