CF1388E.Uncle Bogdan and Projections

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 \lt 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.

回到岸上后，鲍格丹叔叔通常会去电脑俱乐部“摇滚”（The Rock），在愉快的氛围中解题。一天，鲍格丹叔叔遇到了一位老朋友，这位朋友给他出了一道特别的题目……

平面上有 $n$ 条互不相交的水平线段，所有线段的端点均位于整数坐标处，且全部严格位于 $OX$ 轴上方（即标准笛卡尔坐标系中）。你可以任选一个向量 $(a, b)$，其中 $b \lt 0$，且 $a, b$ 均为实数，然后将所有线段沿该向量方向投影到 $OX$ 轴上。这些投影彼此不能相交，但可以相互接触。

求最右侧投影的右端点的 $x$ 坐标与最左侧投影的左端点的 $x$ 坐标之差的最小可能值。

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 \lt 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.

第一行包含一个整数 $n$（$1 \le n \le 2000$）—— 表示线段的数量。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $xl_i$、$xr_i$ 和 $y_i$（$-10^6 \le xl_i \lt xr_i \le 10^6$；$1 \le y_i \le 10^6$）—— 表示对应线段的坐标。

保证这些线段互不相交且互不接触。

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}$.

输出你能得到的最小可能差值。

如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，若你的答案为 $a$，评测组的答案为 $b$，则当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，你的答案视为正确。

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}$

在第一个例子中，如果我们沿向量 $(1, -1)$ 投影线段，则得到答案 $12-3=9$，且（可以证明）无法得到更小的值。

在第二个例子中，沿向量 $(1, -3)$ 投影是最优的。答案为 $8\frac{2}{3}-2\frac{1}{3}=6\frac{1}{3}$。