一名囚犯想要越狱。监狱由顶点为 $$$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