Prison Break
Contest: Codeforces Global Round 11
Difficulty rating: 3500
Tags: binary search, games, geometry, ternary search

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.

Input format:
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.

Output format:
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}$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
2
0 0
223 464
0 749

Example output:
1

Example input:
3
0 0
2 2
2 4
0 6

Example output:
1.0823922

Editorial:
We fix the unit of measure and say that the prisoner moves at $$$1$$$ meter per second.
Let us parametrize the boundary of the prison as follows (ignoring the very long, very high walls). Start walking with speed $$$1$$$ from $$$P_1$$$ towards $$$P_{n+1}$$$ staying on the prison wall and let $$$\gamma(t)$$$ be the point you are at after time $$$t$$$ (so $$$\gamma$$$ is a curve with speed $$$1$$$). Let $$$L$$$ be the total length of such curve (i.e., $$$\gamma(L)=P_{n+1}$$$). With an abuse of notation, we will denote with $$$\gamma$$$ also the image of $$$\gamma$$$ (i.e., the climbable walls).
A criterion for the prison break
The prisoner can escape if and only if there are three times $$$0\le t_1<t_2<t_3\le L$$$ such that $$$$$$\quad |\gamma(t_2)-\gamma(t_1)| < \frac{t_2-t_1}{v} \quad \text{ and } |\gamma(t_3)-\gamma(t_2)| < \frac{t_3-t_2}{v} \,.\tag{$\star$}$$$$$$
proof.
If there are three times $$$t_1<t_2<t_3$$$ such that $$$(\star)$$$ holds, then the prisoner can escape. The strategy of the prisoner is as follows.
He begins by going (very close) to the point $$$\gamma(t_2)$$$. If there is not a guard there, he escapes. Otherwise, there must be a guard at (a point very close to) $$$\gamma(t_2)$$$. Without loss of generality we may assume that the other guard is at $$$\gamma(t)$$$ with $$$t<t_2$$$. Then the prisoner goes directly to $$$\gamma(t_3)$$$ and escapes from there. Notice that the prisoner reaches $$$\gamma(t_3)$$$ in $$$|\gamma(t_3)-\gamma(t_2)|$$$ seconds, while the closest guard (the one at $$$\gamma(t_2)$$$) needs $$$\frac{t_3-t_2}v$$$ seconds. The assumption guarantees that the prisoner reaches $$$\gamma(t_3)$$$ before the guard.
If there are not three such times such that $$$(\star)$$$ holds, then the guards have a strategy to avoid the prison break. This implication is harder; we split its proof into various steps.
The strategy of the guards is encoded by two functions $$$f_1,f_2$$$. Assume that we are given two functions $$$f_1,f_2:\mathcal Z\to [0,L]$$$, where $$$\mathcal Z$$$ denotes the interior of the prison, such that they are both $$$v$$$-Lipschitz (i.e., $$$|f(A)-f(B)|\le v|A-B|$$$) and, for any $$$0\le t\le L$$$, either $$$f_1(\gamma(t))=t$$$ or $$$f_2(\gamma(t))=t$$$ (or also both). Denoting with $$$Q$$$ the position of the prisoner, the guards may follow the following strategy (it is easy to adapt this strategy to the fact that initially the guards are at $$$P_1$$$, we leave it to the reader):
• The first guard will always be at $$$\gamma(f_1(Q))$$$.
• The second guard will always be at $$$\gamma(f_2(Q))$$$.
Extending Lipschitz functions. It remains to construct two such functions $$$f_1,f_2$$$. The idea is to define them on $$$\gamma$$$ and then extend them inside $$$\mathcal Z$$$ through a standard technique. Assume that we are able to define them on $$$\gamma$$$, it is well-known that a real-valued Lipschitz function defined on a subset of a metric space (the metric space is $$$\mathcal Z$$$, its subset is $$$\gamma$$$) can be extended to the whole metric space without increasing the Lipschitz constant (this may sound as abstract nonsense, but it's easy... prove it!).
From two functions to two subsets. The existence of the desired $$$f_1,f_2$$$ boils down to finding two functions on $$$\gamma$$$ that are $$$v$$$-Lipschitz and for each $$$0\le t\le L$$$ we have either $$$f_1(\gamma(t))=t$$$ or $$$f_2(\gamma(t))=t$$$. Let $$$\gamma_1,\gamma_2$$$ be the subsets of $$$\gamma$$$ where, respectively, $$$f_1(\gamma(t))=t$$$ and $$$f_2(\gamma(t))=t$$$. What can we say on the two subsets $$$\gamma_1$$$ and $$$\gamma_2$$$? Well, restricted on them, the function $$$\gamma(t)\mapsto t$$$ must be $$$v$$$-Lipschitz! Thus, applying again the extension argument described above, the problem reduces to finding two subsets $$$\gamma_1,\gamma_2$$$ of $$$\gamma$$$ such that $$$\gamma_1\cup\gamma_2=\gamma$$$ and the function $$$\gamma(t)\mapsto t$$$ is $$$v$$$-Lipschitz on $$$\gamma_1$$$ and $$$\gamma_2$$$.
Existence of the subsets via a bipartition argument. We have finally arrived at the core of the proof, constructing $$$\gamma_1$$$ and $$$\gamma_2$$$. Given two points $$$\gamma(s)$$$ and $$$\gamma(t)$$$, we say that they are compatible if $$$v|\gamma(s)-\gamma(t)| \ge |s-t|$$$. The conditions on $$$\gamma_1$$$ and $$$\gamma_2$$$ are equivalent to:
• It holds $$$\gamma_1\cup\gamma_2=\gamma$$$.
• Any two points in $$$\gamma_1$$$ are compatible.
• Any two points in $$$\gamma_2$$$ are compatible.
Computing the minimal speed $$$v$$$
In order to find the minimal $$$v$$$ such that the guards can avoid the prison break, we binary search the answer. Given a certain $$$v$$$, we must check whether there are three times $$$0\le t_1<t_2<t_3\le L$$$ such that $$$(\star)$$$ holds.
We say that $$$t_2$$$ is left-incompatible if there is a $$$t_1<t_2$$$ such that $$$(\star)$$$ holds and we say that it is right-incompatible if there is a $$$t_3>t_2$$$ such that $$$(\star)$$$ holds. We have to check whether there is a time that is both left-incompatible and right-incompatible.
Let us assume that $$$\gamma(t_1)\in [P_i,P_{i+1}]$$$ and $$$\gamma(t_2)\in[P_j,P_{j+1}]$$$ with $$$i < j$$$. Under this additional constraint, characterizing the "left-incompatible" times $$$t_2$$$ reduces to finding all the points $$$\gamma(t_2)\in[P_j,P_{j+1}]$$$ such that $$$$$$ \min_{\gamma(t_1)\in[P_i,P_{i+1}]} |\gamma(t_2)-\gamma(t_1)|-\frac{t_2-t_1}{v} < 0 \,.$$$$$$ There are many different approaches to characterize the set of left-incompatible times $$$t_2$$$. The crucial observation that is common to all the approaches is that the set of left-incompatible $$$t_2$$$ is the union of $$$O(1)$$$ intervals (actually it is an interval, but this observation is not necessary for all the approaches). We present two such methods:
• The first method, based on solving quadratic equations, needs some care to avoid precision issues/division by zero. The complexity is $$$O(1)$$$ (once $$$i$$$ and $$$j$$$ are fixed) and produces a complete algorithm with complexity $$$O(n^2\log(n)\log(\varepsilon^{-1}))$$$ (or a slightly easier to implement $$$O(n^3\log(\varepsilon^{-1}))$$$ that is super-fast.
• The second method, based on ternary search, is pretty straight-forward to implement but proving its correctness is rather hard. The complexity is $$$O(\log(\varepsilon^{-1})^2)$$$ and produces a complete algorithm with complexity $$$O(n^2\log(\varepsilon^{-1})^3 + n^3\log(\varepsilon^{-1}))$$$ which is rather slow in practice; some care might be necessary to get it accepted.
Since we will need them in both approaches, let us define $$$t^{\pm}_{12}$$$ as the values such that $$$\gamma(t_1^-)=P_i$$$, $$$\gamma(t_1^+)=P_{i+1}$$$, $$$\gamma(t_2^-)=P_j$$$, $$$\gamma(t_2^+)=P_{j+1}$$$.
Via quadratic equations. Consider the function $$$F(t_1,t_2):= |\gamma(t_2)-\gamma(t_1)|^2v^2-(t_2-t_1)^2$$$. We have to find the values $$$t_2\in[t_2^-,t_2^+]$$$ such that $$$$$$ \min_{t_1\in [t_1^-,t_1^+]} F(t_1, t_2) < 0\,.$$$$$$ Notice that $$$t_1\mapsto F(t_1,t_2)$$$ is a quadratic polynomial with positive leading coefficient. Hence the minimum is either at an extreme point $$$t_1\in \{t_1^-,t_1^+\}$$$ or at the point $$$t_1=:f(t_2)$$$ such that $$$\partial_{t_1}F(t_1,t_2)=0$$$. Moreover $$$t_2\mapsto F(t_1^-,t_2)$$$ and $$$t_2\mapsto F(t_1^+, t_2)$$$ and $$$t_2\mapsto F(f(t_2), t_2)$$$ are all quadratic polynomials, so the set of times $$$t_2$$$ where they are negative is either an interval or a union of two intervals (which can be found finding the roots of the appropriate quadratic equations). Since $$$f(t_2)\in[t_1^-,t_1^+]$$$ holds for $$$t_2$$$ in an interval (with easy to find extreme points), the solution is complete.
Let us remark that, even if everything seems elementary and easy, implementing this is not a cakewalk.
Via ternary search. Consider the function $$$G(t_1,t_2):= \frac{|\gamma(t_2)-\gamma(t_1)|}{t_2-t_1}$$$. We have to find the values $$$t_2\in[t_2^-,t_2^+]$$$ such that $$$$$$ \min_{t_1\in[t_1^-,t_1^+]} G(t_1, t_2) < v^{-1} \,.$$$$$$ The function $$$t_1\mapsto G(t_1,t_2)$$$ is unimodal, hence, given $$$t_2$$$, with a ternary search we may compute $$$$$$ \tilde G(t_2) := \min_{t_1\in[t_1^-, t_1^+]} G(t_1, t_2) \,.$$$$$$ Then, also the function $$$t_2\mapsto \tilde G(t_2)$$$ is unimodal, hence with a ternary search+binary search we may find the interval where it is below $$$v^{-1}$$$.
For a proof that the above functions are really unimodal, take a look at this short pdf.
Implementing this second approach might be a bit tedious, but presents no real difficulty. Since this is quite slow, it might need some care to get accepted (for example, the arg-min of $$$\tilde G$$$ shall be computed only once and not for each binary-search iteration on $$$v$$$).