← 返回题目列表

Codeforces · 1388/E

E. 博格丹叔叔和预测

中文机器翻译题面 查看原题

回到岸上后,博格丹叔叔通常会去电脑俱乐部“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}$$$