分数: 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) 按逆时针顺序形成凸多边形。
- 没有三点 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 is 5.650281...。我们可以证明它是最小值。 请注意,您可以输入周长 C.
请注意,如果绝对或相对误差最多为,则您的输出被认为是正确的 10^{-6}。 例如,输出类似 5.650287 也被认为是正确的。
示例输入 2
3 0 0 2 0 1 10 3 7 10 3
示例输出 2
8.06225774829854965279