CF1427H.Prison Break

A prisoner wants to escape from a prison. The prison is represented by the interior of the convex polygon with vertices $P_1, P_2, P_3, \ldots, P_{n+1}, P_{n+2}, P_{n+3}$. It holds $P_1=(0,0)$, $P_{n+1}=(0, h)$, $P_{n+2}=(-10^{18}, h)$ and $P_{n+3}=(-10^{18}, 0)$.

The prison walls $P_{n+1}P_{n+2}$, $P_{n+2}P_{n+3}$ and $P_{n+3}P_1$ are very high and the prisoner is not able to climb them. Hence his only chance is to reach a point on one of the walls $P_1P_2, P_2P_3,\dots, P_{n}P_{n+1}$ and escape from there. On the perimeter of the prison, there are two guards. The prisoner moves at speed $1$ while the guards move, remaining always on the perimeter of the prison, with speed $v$.

If the prisoner reaches a point of the perimeter where there is a guard, the guard kills the prisoner. If the prisoner reaches a point of the part of the perimeter he is able to climb and there is no guard there, he escapes immediately. Initially the prisoner is at the point $(-10^{17}, h/2)$ and the guards are at $P_1$.

Find the minimum speed $v$ such that the guards can guarantee that the prisoner will not escape (assuming that both the prisoner and the guards move optimally).

Notes:

• At any moment, the guards and the prisoner can see each other.
• The "climbing part" of the escape takes no time.
• You may assume that both the prisoner and the guards can change direction and velocity instantly and that they both have perfect reflexes (so they can react instantly to whatever the other one is doing).
• The two guards can plan ahead how to react to the prisoner movements.

一名囚犯想要越狱。监狱由一个凸多边形的内部表示，其顶点依次为 $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$。

若囚犯抵达周界上某一点时该点恰有一名守卫，则守卫会立即将其击毙；若囚犯抵达可攀爬段（即 $P_1P_2, P_2P_3, \dots, P_nP_{n+1}$ 中的某一段）上的某一点，且该点无守卫，则他立即成功逃脱。初始时刻，囚犯位于点 $(-10^{17}, h/2)$，两名守卫均位于 $P_1$。

求最小的守卫速度 $v$，使得守卫总能保证囚犯无法逃脱（假设囚犯与守卫均采取最优策略）。

注：

• 在任意时刻，守卫与囚犯彼此可视。
• “攀爬逃脱”过程不消耗时间。
• 可假设囚犯与守卫均可瞬间改变方向与速度，且反应能力完美（即能即时响应对方的任何动作）。
• 两名守卫可预先共同制定策略，以应对囚犯的各种移动行为。

The first line of the input contains $n$ ($1 \le n \le 50$).

The following $n+1$ lines describe $P_1, P_2,\dots, P_{n+1}$. The $i$-th of such lines contain two integers $x_i$, $y_i$ ($0\le x_i, y_i\le 1,000$) — the coordinates of $P_i=(x_i, y_i)$.

It is guaranteed that $P_1=(0,0)$ and $x_{n+1}=0$. The polygon with vertices $P_1,P_2,\dots, P_{n+1}, P_{n+2}, P_{n+3}$ (where $P_{n+2}, P_{n+3}$ shall be constructed as described in the statement) is guaranteed to be convex and such that there is no line containing three of its vertices.

输入的第一行包含一个整数 $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}$ 按题目描述构造）保证是凸的，且其任意一条直线上至多经过该多边形的两个顶点。

Print a single real number, the minimum speed $v$ that allows the guards to guarantee that the prisoner will not escape. Your answer will be considered correct if its relative or absolute error does not exceed $10^{-6}$.

输出一个实数，即守卫能够确保囚犯无法逃脱的最小速度 $v$。只要你的答案的相对误差或绝对误差不超过 $10^{-6}$，即视为正确。