← 返回题目列表

Codeforces · 1427/H

H. 越狱

中文机器翻译题面 查看原题

一名囚犯想要越狱。监狱由顶点为 $$$P_1、P_2、P_3、\ldots、P_{n+1}、P_{n+2}、P_{n+3}$$$ 的凸多边形的内部表示。它包含 $$$P_1=(0,0)$$$、$$$P_{n+1}=(0, h)$$$、$$$P_{n+2}=(-10^{18}, h)$$$ 和 $$$P_{n+3}=(-10^{18}, 0)$$$。

监狱围墙 $$$P_{n+1}P_{n+2}$$$、$$$P_{n+2}P_{n+3}$$$ 和 $$$P_{n+3}P_1$$$ 非常高,囚犯无法攀爬。因此,他唯一的机会是到达墙上的一个点 $$$P_1P_2, P_2P_3,\dots, P_{n}P_{n+1}$$$ 并从那里逃脱。监狱的外围,有两名看守。囚犯以 $$$1$$$ 的速度移动,而警卫以 $$$v$$$ 的速度移动,始终保持在监狱的周边。

如果囚犯到达有守卫的周界点,守卫就会杀死囚犯。如果囚犯到达他能够攀爬的周界部分的某个点并且那里没有警卫,他会立即逃脱。最初,囚犯位于 $$$(-10^{17}, h/2)$$$ 点,看守位于 $$$P_1$$$。

求警卫能够保证囚犯不会逃跑的最小速度$$$v$$$(假设囚犯和警卫都以最佳移动速度)。

注意:

- 警卫和囚犯随时可以看到对方。
- 逃生的“攀爬部分”不需要时间。
- 你可能会假设囚犯和警卫都可以立即改变方向和速度,并且他们都有完美的反应能力(因此他们可以立即对对方所做的任何事情做出反应)。
- 两名警卫可以提前计划如何对囚犯的动作做出反应。

输入

输入的第一行包含 $$$n$$$ ($$$1 \le n \le 50$$$)。

以下 $$$n+1$$$ 行描述 $$$P_1, P_2,\dots, P_{n+1}$$$。这些行的第 $$$i$$$ 包含两个整数 $$$x_i$$$、$$$y_i$$$ ($$$0\le x_i, y_i\le 1,000$$$) — $$$P_i=(x_i, y_i)$$$ 的坐标。

保证 $$$P_1=(0,0)$$$ 且 $$$x_{n+1}=0$$$。具有顶点 $$$P_1,P_2,\dots, P_{n+1}, P_{n+2}, P_{n+3}$$$ 的多边形(其中 $$$P_{n+2}, P_{n+3}$$$ 应按照语句中的描述构造)保证是凸的,并且不存在包含其三个顶点的线。

输出

打印一个实数,即让看守保证囚犯不会逃跑的最低速度$$$v$$$。如果相对或绝对误差不超过 $$$10^{-6}$$$,您的答案将被视为正确。

示例

输入 #1

2
0 0
223 464
0 749

输出 #1

1

输入 #2

3
0 0
2 2
2 4
0 6

输出 #2

1.0823922

输入 #3

4
0 0
7 3
7 4
5 7
0 8

输出 #3

1.130309669

输入#4

5
0 0
562 248
460 610
281 702
206 723
0 746

输出#4

1.148649561

输入 #5

7
0 0
412 36
745 180
747 184
746 268
611 359
213 441
0 450

输出 #5

1.134745994