← 返回题目列表

Codeforces · 1071/E

E. 防雨

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

很多人梦想拥有敞篷车(通常也称为敞篷车)。然而,有些敞篷车根本没有车顶,很容易被雨淋到。这就是著名发明家 Melon Ask 决定为敞篷车打造防雨机制的原因。

该机构的工作场所是驾驶员正上方的飞机的一部分。其功能部分由两条导轨组成,导轨的滑动端点为一根拉伸绳。为了简单起见,我们可以将其视为带有绳索段的平面中的一对平行线段,我们可以自由选择其端点作为这些轨道段上的任何点。

该机制的算法部分检测每个特定的雨滴并预测它到达飞机的时间和地点。此时,绳子段必须包含雨滴点(因此绳子会吸收雨滴)。

您将获得绳索端点的初始位置以及有关雨滴的所有信息。你要选择端点滑动的最小可能速度$$$v$$$(两个端点可以相互独立地沿其线段向任何方向滑动),这样就可以捕获所有以不大于$$$v$$$的速度移动两个端点的雨滴,或者发现无论速度有多高都是不可能的。

输入

第一行包含三个整数 $$$n$$$、$$$w$$$ 和 $$$h$$$ ($$$1 \le n \le 10^5$$$, $$$1\le w, h \le 10^3$$$),表示有 $$$n$$$ 雨滴,两条铁轨表示为连接 $$$(0, 0)$$$ 的线段和 $$$(w, 0)$$$ 并连接 $$$(0, h)$$$ 和 $$$(w, h)$$$。

第二行包含两个整数$$$e_1$$$和$$$e_2$$$,表示端点的初始位置(即此时$$$t = 0$$$)为$$$(e_1, 0)$$$和$$$(e_2, h)$$$ ($$$0\le e_1, e_2\le w$$$)。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含三个整数 $$$t_i$$$、$$$x_i$$$ 和 $$$y_i$$$ ($$$1\le t_i\le 10^5$$$、$$$0\le x_i \le w$$$、$$$0 < y_i < h$$$) 意味着第 $$$i$$$ 个雨滴在 $$$t_i$$$ 时刻在 $$$(x_i, y_i)$$$ 点接触平面。对于所有有效的$$$i$$$,保证$$$t_i \le t_{i+1}$$$。

输出

如果不可能捕捉到所有雨滴,请打印 $$$-1$$$。

否则,打印可以捕获所有绳索端点的最小可能最大速度。如果绝对或相对误差不超过 $$$10^{-4}$$$,则认为您的答案是正确的。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。如果 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$,则认为您的答案是正确的。

示例

输入 #1

3 5 5
0 0
1 1 4
2 2 4
3 3 4

输出 #1

1.0000000019

输入 #2

2 5 5
0 0
2 4 1
3 1 4

输出 #2

2.1428571437

输入 #3

3 5 5
0 0
1 2 1
1 3 3
1 4 2

输出 #3

-1

注意

这就是在第一个样本测试中可以采取的行动:

第二个也是一样: