← 返回题目列表

AtCoder · abc286_h

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) 按逆时针顺序形成凸多边形。
  • 没有三点 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

下图显示了实现最短距离的一种方法。

image

如果您旅行的身份为 (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