回到岸上后,博格丹叔叔通常会去电脑俱乐部“The Rock”,在愉快的公司里解决任务。有一天,博格丹叔叔遇到了他的好老朋友,他告诉他一项不寻常的任务......
在标准笛卡尔坐标系的平面上,有 $$$n$$$ 个不相交的水平线段,其末端为整数点。所有段都严格位于 $$$OX$$$ 轴上方。您可以选择任意向量 ($$$a$$$, $$$b$$$),其中 $$$b < 0$$$ 且坐标为实数,并将所有线段沿该向量投影到 $$$OX$$$ 轴。投影不应相交,但可以相互接触。
求最右边投影右端的 $$$x$$$ 坐标与最左边投影左端的 $$$x$$$ 坐标之间的最小可能差异。
输入
第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — 段数。
接下来的 $$$n$$$ 行的第 $$$i$$$ 包含三个整数 $$$xl_i$$$、$$$xr_i$$$ 和 $$$y_i$$$ ($$$-10^6 \le xl_i < xr_i \le 10^6$$$; $$$1 \le y_i \le 10^6$$$)—相应线段的坐标。
保证线段不相交或接触。
输出
打印出您可以获得的最小可能差异。
如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,如果您的答案是 $$$a$$$ 并且陪审团的答案是 $$$b$$$,那么如果 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$,您的答案将被视为正确。
示例
输入 #1
3 1 6 2 4 6 4 4 6 6
输出 #1
9.000000000
输入 #2
3 2 5 1 4 6 4 7 8 2
输出 #2
6.333333333
输入 #3
2 1 3 1 4 7 1
输出 #3
6.000000000
注意
在第一个例子中,如果我们沿着向量 $$$(1, -1)$$$ 投影线段,那么我们会得到答案 $$$12-3=9$$$ 并且(可以证明)不可能得到更少的答案。
在第二个示例中,最好沿着向量 $$$(1, -3)$$$ 进行投影。答案是 $$$8\frac{2}{3}-2\frac{1}{3}=6\frac{1}{3}$$$