Uncle Bogdan and Projections
Contest: Codeforces Round 660 (Div. 2)
Difficulty rating: 2700
Tags: data structures, geometry, sortings

After returning to shore, uncle Bogdan usually visits the computer club "The Rock", to solve tasks in a pleasant company. One day, uncle Bogdan met his good old friend who told him one unusual task...

There are $$$n$$$ non-intersecting horizontal segments with ends in integers points on the plane with the standard cartesian coordinate system. All segments are strictly above the $$$OX$$$ axis. You can choose an arbitrary vector ($$$a$$$, $$$b$$$), where $$$b < 0$$$ and coordinates are real numbers, and project all segments to $$$OX$$$ axis along this vector. The projections shouldn't intersect but may touch each other.

Find the minimum possible difference between $$$x$$$ coordinate of the right end of the rightmost projection and $$$x$$$ coordinate of the left end of the leftmost projection.

Input format:
The first line contains the single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of segments.

The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$xl_i$$$, $$$xr_i$$$ and $$$y_i$$$ ($$$-10^6 \le xl_i < xr_i \le 10^6$$$; $$$1 \le y_i \le 10^6$$$) — coordinates of the corresponding segment.

It's guaranteed that the segments don't intersect or touch.

Output format:
Print the minimum possible difference you can get.

Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.

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

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

Note:
In the first example if we project segments along the vector $$$(1, -1)$$$ then we get an answer $$$12-3=9$$$ and (it can be proven) it is impossible to get less.

It is optimal to project along the vector $$$(1, -3)$$$ in the second example. The answer is $$$8\frac{2}{3}-2\frac{1}{3}=6\frac{1}{3}$$$

Example input:
3
1 6 2
4 6 4
4 6 6

Example output:
9.000000000

Example input:
3
2 5 1
4 6 4
7 8 2

Example output:
6.333333333

Editorial:
It is easy to understand that there is an optimal vector at which the value we need is minimal and at least one pair of projections is touching. Note also that the vector is completely described by the angle between it and the positive direction of the $$$ OX $$$ axis. If two line segments are at different heights, then there are two ways to select a vector so that their projections touch. Let's find two angles that describe these vectors. If we project along a vector with an angle that is in the interval that the found two angles form, then the projections will intersect. So, this range of angles is 'forbidden'. Using the scanline method, we can find such angles that they are the boundaries of some 'forbidden' interval and do not fall into any 'forbidden' interval. Then we only need to check these angles.
We also need to quickly find the rightmost and leftmost points for each angle. Let's take two points at different heights. Let them project to one point with a vector with an angle $$$\alpha$$$. Then on the interval $$$(0^\circ;\alpha)$$$ the upper one will be to the right, and on the interval $$$ (\alpha; 180^\circ)$$$ the upper one will be to the left. We will process two types of requests using the scanning line:
1. Check the answer for the current angle;
2. Swap two points. It is necessary to carefully handle the case when, at some angle, several points are swapped.
Alternative way: if you project the point $$$(x; y)$$$ along the vector with the angle $$$\alpha$$$, you get the point $$$(x + y * ctg (\ alpha); 0)$$$. We'll use the Convex Hull Trick to quickly find the rightmost and leftmost points for each angle. We will store CHT for maximums and minimums with lines $$$ k = y_i, b = x_i $$$. Queries at $$$ctg(\alpha)$$$ will give us the leftmost and rightmost points.
It is a corner case if all points are at the same height. Then the answer is $$$max(xr_i) - min(xl_i)$$$.
Complexity of solution - $$$O(n^2log(n))$$$.