← 返回题目列表

Codeforces · 832/C

C. 奇怪的辐射

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

n 个人站在正整数坐标严格小于 106 的坐标轴上。对于每个人,我们知道他面向哪个方向(左或右),以及他的最大速度。

你可以在某个坐标为非负整数的点放置炸弹,然后将其炸毁。这一刻,所有人都会开始以最快的速度,朝着自己所面对的方向奔跑。此外,两束奇怪的射线将以速度 s 开始从炸弹传播:一束向右,一束向左。当然,速度s严格大于人的最大速度。

射线很奇怪,因为如果在任何时刻某些射线和某个人的位置和运动方向一致,那么人的速度会立即随着射线的速度而增加。

你需要将炸弹放置在这样一个点上,即有人跑过点0,有人跑过点106的最短时间时刻尽可能小。换句话说,找到最小时刻 t,使得有一个点可以放置炸弹,这样在时刻 t 有人跑过 0 点,有人跑过点 106。

输入

第一行包含两个整数 n 和 s (2 ≤ n ≤ 105, 2 ≤ s ≤ 106) — 人数和射线速度。

接下来的 n 行包含人物的描述。第 i 行包含三个整数 xi、vi 和 ti(0 < xi < 106, 1 ≤ vi < s, 1 ≤ ti ≤ 2)——分别是线上第 i 个人的坐标、他的最大速度和他将要跑的方向(1 是向左,即坐标减少的方向,2 是向右,即坐标增加的方向)。

保证无论炸弹的位置如何都能到达点 0 和 106。

输出

打印到达点 0 和 106 所需的最短时间。

如果您的答案的绝对或相对误差不超过 10 - 6,则认为您的答案是正确的。也就是说,如果您的答案是 a,陪审团的答案是 b,那么您的答案将被接受,如果 $${ \frac { | } a - b | } { \operatorname* { m a x } ( 1, | b | ) } } \leq 1 0 ^ { - 6 }$$。

示例

输入 #1

2 999
400000 1 2
500000 1 1

输出 #1

500000.000000000000000000000000000000

输入 #2

2 1000
400000 500 1
600000 500 2

输出 #2

400.000000000000000000000000000000

注意

在第一个例子中,炸弹最好放置在坐标为 400000 的点上。那么在 0 时刻,第一个人的速度变为 1000,在 600 时刻到达 106 点。炸弹不会对第二个人产生影响,他会在 500000 时刻到达 0 点。

在第二个例子中,最好将炸弹放置在点500000。射线将在时间200时追上两个人。此时,第一个在坐标为300000的点,第二个在坐标为700000的点。他们的速度将变为1500,在时间400时,他们将同时穿过点0和106。