Rain Protection
Contest: Codeforces Round 517 (Div. 1, based on Technocup 2019 Elimination Round 2)
Difficulty rating: 3500
Tags: binary search, geometry

A lot of people dream of convertibles (also often called cabriolets). Some of convertibles, however, don't have roof at all, and are vulnerable to rain. This is why Melon Ask, the famous inventor, decided to create a rain protection mechanism for convertibles.

The workplace of the mechanism is a part of plane just above the driver. Its functional part consists of two rails with sliding endpoints of a piece of stretching rope. For the sake of simplicity we can consider this as a pair of parallel segments in a plane with the rope segment, whose endpoints we are free to choose as any points on these rails segments.

The algorithmic part of the mechanism detects each particular raindrop and predicts when and where it reaches the plane. At this exact moment the rope segment must contain the raindrop point (so the rope adsorbs the raindrop).

You are given the initial position of the rope endpoints and all information about raindrops. You are to choose the minimal possible speed $$$v$$$ of the endpoints sliding (both endpoints can slide in any direction along their segments independently of each other) in such a way that it is possible to catch all raindrops moving both endpoints with speed not greater than $$$v$$$, or find out that it's impossible no matter how high the speed is.

Input format:
The first line contains three integers $$$n$$$, $$$w$$$ and $$$h$$$ ($$$1 \le n \le 10^5$$$, $$$1\le w, h \le 10^3$$$), meaning that there are $$$n$$$ raindrops, and two rails are represented as segments connecting $$$(0, 0)$$$ and $$$(w, 0)$$$ and connecting $$$(0, h)$$$ and $$$(w, h)$$$.

The second line contains two integers $$$e_1$$$ and $$$e_2$$$, meaning that the initial (that is, at the moment $$$t = 0$$$) positions of the endpoints are $$$(e_1, 0)$$$ and $$$(e_2, h)$$$ ($$$0\le e_1, e_2\le w$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$t_i$$$, $$$x_i$$$ and $$$y_i$$$ ($$$1\le t_i\le 10^5$$$, $$$0\le x_i \le w$$$, $$$0 < y_i < h$$$) meaning that the $$$i$$$-th raindrop touches the plane at the point $$$(x_i, y_i)$$$ at the time moment $$$t_i$$$. It is guaranteed that $$$t_i \le t_{i+1}$$$ for all valid $$$i$$$.

Output format:
If it is impossible to catch all raindrops, print $$$-1$$$.

Otherwise, print the least possible maximum speed of the rope endpoints for which it is possible to catch them all. Your answer is considered correct if the absolute or relative error doesn't exceed $$$10^{-4}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is considered correct if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.

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

Note:
That is how one can act in the first sample test:

Here is the same for the second:

Example input:
3 5 5
0 0
1 1 4
2 2 4
3 3 4

Example output:
1.0000000019

Example input:
2 5 5
0 0
2 4 1
3 1 4

Example output:
2.1428571437

Editorial:
First, let's find out if we can catch all raindrops for a fixed speed $$$v$$$.
Assume that the endpoints are at $$$(e_1, 0)$$$ and $$$(e_2, h)$$$ at any moment. Consider the point $$$(e_1, e_2)$$$ for this state (we call it the state point for this state). From now on we work with these points. We know that this state point can move with speed at most $$$v$$$ in both directions independently, that is, if the state point is $$$(x, y)$$$ at the moment $$$t$$$, then it'll be in $$$[x - v\cdot\text{d}t, x + v\cdot\text{d}t]\times[y - v\cdot\text{d}t, y + v\cdot\text{d}t]$$$ at the moment $$$t + \text{d}t$$$.
It turns out that for each $$$i$$$ one of the following takes place:
• we cannot catch raindrops from $$$1$$$ to $$$i$$$;
• we can catch these raindrops and there is exactly one possible option for the state point at the moment $$$t_i$$$;
• we can catch these raindrops and there is a segment on the plane such that the state point at the moment $$$t_i$$$ can be in any point of this segment and nowhere else.
Indeed, we prove this by induction. Its basis for $$$t_0 = 0$$$ is trivial. Let's prove its step.
• If we cannot catch raindrops from $$$1$$$ to $$$i$$$ then we cannot catch all raindrops from $$$1$$$ to $$$i + 1$$$.
• If there is some segment where the state point can be at $$$t_i$$$ (possibly a segment of length $$$0$$$) then at the moment $$$t_{i+1}$$$ the state point can be anywhere inside the convex hull of the union of two squares. The squares are $$$[x - v\cdot\text{d}t, x + v\cdot\text{d}t]\times[y - v\cdot\text{d}t, y + v\cdot\text{d}t]$$$ for the endpoints $$$(x, y)$$$ of the segment at $$$t_i$$$, and here $$$\text{d}t$$$ is $$$t_{i + 1} - t_i$$$.But we also know that the rope must contain one particular point at the moment $$$t_{i+1}$$$, which can be expressed as a linear equation of the state point at the moment $$$t_{i+1}$$$. So to obtain the required segment for $$$t_{i+1}$$$ one should intersect a line with a convex hull of $$$8$$$ points (which is in fact no more than a hexagon).However, it's not all: the endpoints of the rope mustn't leave the rails which means that the convex hull should be first intersected with the rectangle $$$[0, w]\times[0, w]$$$. However, it can be done after intersecting with the required line.
So the solution now is the following:
• First we check if the answer is $$$-1$$$. This is the case when there is a triple of non-collinear raindrop points which should be on the rope simultaneously or there is a raindrop which is not on the rope at the moment $$$0$$$, while it should be. The simplest way to check it is to check if we can catch all raindrops with speed $$$w$$$. First, it involves no case handling; second, we will use this function later anyway.
• After this we run a binary search to find the minimal possible value for speed in such a way that it's possible to catch all the raindrops.
That's the idea of the solution. Now let's consider precision issues.
The explanation below contains some notions which may be new for a particular reader. Please don't be afraid of them, I explain what they mean right after introducing them. I refer to them by their names first for readers familiar with these notions to get the point faster and maybe skip the explanation which follows. For anyone who doesn't want to read the full proof and wants to know the summary: long double precision should be enough to get AC with the solution above (handling lines intersections properly).
Define a function $$$f_i(v)$$$ as the $$$\ell_{\infty}$$$-diameter of the set of possible locations of the state point at the moment $$$t_i$$$ for the speed $$$v$$$, that is,
• $$$f_i(v) = 0$$$ if this set is empty or consists of a single point;
• $$$f_i(v) = \max\left(|x_1 - x_2|, |y_1 - y_2|\right)$$$ if this set is a segment between $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$.
In other words, every time we calculate the length of any segment, we do it in this metric, since it'll be convenient for our purposes.
Let $$$\hat{v}$$$ be the correct answer, and let $$$\varepsilon$$$ be a sufficiently small positive number (but still much bigger than the machine epsilon, of course).
One can see that all $$$t_i$$$-s can be divided into two groups which differ a lot by their meaning:
• those for which we must catch one raindrop at this moment (or many equal raindrops, which doesn't matter),
• those for which we must catch more than one raindrop at this moment.
For the first ones we basically need to intersect a polygon with a line, but for the second ones the state point at $$$t_i$$$ can be determined and doesn't depend on the speed (or such $$$t_i$$$-s force our algorithm to tell that the goal is impossible in the very beginning). Let's call the raindrops with $$$t_i$$$ of the first type simple, and the others complicated.
Let's prove the following lemmas:
Lemma 1a. Let $$$i$$$ be an index of a simple raindrop. For $$$v = \hat{v} + \varepsilon$$$ each $$$f_i(v)$$$ is at least $$$\varepsilon$$$.
Lemma 1b. Let $$$i$$$ be an index of a complicated raindrop. For $$$v = \hat{v} + \varepsilon$$$ the corresponding state point position at the moment $$$t_i$$$ is at least $$$\varepsilon$$$ away from the border of a polygon before intersecting with $$$[0, w]\times[0, w]$$$.
Lemma 2. Let $$$idx$$$ be the index of the first raindrop we cannot catch for a value of speed which is very close to $$$\hat{v}$$$ but is less than it. Then for $$$v = \hat{v} - \varepsilon$$$ either our algorithm halts earlier than it handles the $$$idx$$$-th raindrop, or the corresponding line to this raindrop (or the corresponding point if the raindrop is complicated) is at least $$$\varepsilon$$$ away from the corresponding state points polygon (again, in $$$\ell_{\infty}$$$ metric).
One can see that proving these lemmas is sufficient to validate the solution. Indeed, comparing all intersections with quite good precision will move the binary search borders into the $$$(\hat{v} - \varepsilon, \hat{v} + \varepsilon)$$$ interval which is enough to stop for some $$$\varepsilon$$$.
Proof of lemma 1 (both variations). Fix $$$i$$$. We know that the $$$(i-1)$$$-th set $$$S_{i-1}(v)$$$ of possible state points for $$$v = \hat{v}$$$ is not empty (from the definition of $$$\hat{v}$$$). It's clear that the $$$(i-1)$$$-th set for $$$v = \hat{v} + \varepsilon$$$ is a superset of $$$S_{i-1}(\hat{v})$$$, because we can move no faster than with the speed of $$$\hat{v} < \hat{v} + \varepsilon$$$. To get $$$S_i$$$, we move from $$$S_{i-1}$$$ no more than $$$(t_i - t_{i-1})(\hat{v} + \varepsilon) \le (t_i - t_{i-1})\hat{v} + \varepsilon$$$. This finishes the proof of 1b. Since $$$S_i(\hat{v})$$$ is also not empty, $$$S_i(\hat{v} + \varepsilon)$$$ is at least the segment $$$S_i(\hat{v})$$$ plus all the points on the corresponding line at the distance no more than $$$\varepsilon$$$, that is, at least $$$\varepsilon$$$ longer than $$$S_i(\hat{v})$$$, hence is at least $$$\varepsilon$$$ long, qed.
Proof of lemma 2. Assume our algorithm made at least $$$idx$$$ iterations. Consider the corresponding polygon at the moment $$$t_{idx}$$$. We know that for $$$v = \hat{v}$$$
• this polygon intersects the required line/point, but
• its interior doesn't.
That means that each point of the possible set of state points at the moment isn't inside the polygon. That means that if we reduce $$$v$$$ by $$$\varepsilon$$$ then the distance from every point of this set to the polygon is at least $$$\varepsilon$$$, qed.
To summarize, the only precision issue we can meet is when we intersect two or more lines for complicated raindrops. This part can be implemented in integers, but let's dive into this anyway.
One can see that catching raindrop at $$$(x, y)$$$ means that
$$$$$$\frac{y}{x - e_1} = \frac{h - y}{e_2 - x},$$$$$$
or
$$$$$$(e_2 - x)y = (x - e_1)(h - y)\Rightarrow e_1(h-y) + e_2y = xh.$$$$$$
Since the coefficients of this line equation are of order $$$h$$$, the coordinates of its solution are some rationals with the denominator of order $$$1/h^2$$$. If we then want to check if such point belongs to another line, we want to compare some integer divided by another integer which is $$$\le h^2$$$ with the third integer, so we need an epsilon less than $$$1/h^2$$$.