← 返回题目列表

AtCoder · gigacode_2019_e

E. 专车接送

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

配点: 100 点

問題文

Giga街自西向东呈直线延伸,长度 L 这是一米路。

E869120 您最初位于 Giga 街的西端,速度为 V_S 剩余米数 D_S 我开的车可以跑几米。

这条街的意义远不止于此。 有 N 辆车。i 第二辆车是从西端来的 X_i 以米和每分钟为单位 V_i 剩余米数 D_i 您可以运行仪表。

你开车。 从西到东 我想开车到达 Giga Street 的东端。

他也可以开车到沿途有车停的地方,换乘那辆车。连接需要多长时间? 0 分钟就可以了。

现在,他能到达吉加街的东端吗?如果您无法到达,请报告此情况,如果可以,请报告到达东端所需的最短时间(以分钟为单位)。

制約

  • 0 \leq N \leq 2 \ 019
  • 1 \leq L \leq 40 \ 075 \ 017
  • 1 \leq X_1, X_2, \dots, X_N \leq L-1
  • X_1, X_2, \dots, X_N 都不同
  • 1 \leq V_S, V_1, V_2, \dots, V_N \leq 100 \ 000
  • 1 \leq D_S, D_1, D_2, \dots, D_N \leq L
  • 输入全部为整数

部分点

该问题分为多个子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (9 点) N = 0
  2. (6 点) N = 0 或 给出 N = 1
  3. (22 点) N \leq 10
  4. (30 点) V_S = 1 和所有 对于 i 反对 V_i = 1
  5. (33 分) 没有额外的限制。

子任务 4 的提示

这个子任务是判断你是否能到达东端。因为到处都是每分钟的速度 1 它以米为单位移动,所以如果你能到达那里,最短的时间绝对是 因为还有 L 分钟。小任务 如果您正在研究 4 ,您可能也需要考虑此提示。


入力

输入是按以下格式从标准输入给出的。

N L
V_S D_S
X_1 V_1 D_1
X_2 V_2 D_2
 : : :
X_N V_N D_N

出力

如果无论你做什么都无法到达Giga街的东端 请输出 impossible 。
如果您可以到达那里,请输出到达那里所需的最短时间(以分钟为单位)。您可以输出小数点后任意位数,但与答案的误差(绝对误差或相对误差) 仅当答案在 10^{-5} 内时才被认为是正确的。


入力例 1

3 10
1 5
3 5 8
6 10 5
7 2 7

出力例 1

4.000000000000000000000

当你这样移动时: 您可以在 4 分钟内到达 Giga 街的东端,这是最快的。

  • 首先,乘坐你的第一辆车,从西端出发。 3 前往仪表处。对此 需要 3/1 = 3 分钟。
  • 接下来,1 从西端开车 6 前往仪表处。对此 需要 3/5 = 0.6 分钟。
  • 最后,2 从东端(从西端) 继续前往 10 米)。对此 我在 4/10 = 0.4 分钟。
  • 合計 3 + 0.6 + 0.4 = 4 分钟内到达了东端。

入力例 2

3 10
1 5
3 5 8
6 1 5
7 2 7

出力例 2

4.400000000000000355271

当你这样移动时: 您可以在 4.4 分钟内到达 Giga 街的东端,这是最快的。

  • 首先,乘坐你的第一辆车,从西端出发。 3 前往仪表处。对此 需要 3/1 = 3 分钟。
  • 并且,1 从东端(从西端) 继续前往 10 米)。对此 我在 7/5 = 1.4 分钟。
  • 合計 3 + 1.4 = 4.4 分钟内到达了东端。

入力例 3

2 10
1 4
3 1 2
6 1 10

出力例 3

impossible

这种情况下,无论你做什么,都无法到达Giga街的东端。
另外,输入/输出示例 3 是一个小作业 4「V_S = 1、V_i = 1”满足约束。


入力例 4

0 1
99991 1

出力例 4

0.000010000900081007291

答案是 而不是类似 1.00009e-05 请注意,输出的格式应类似于0.00001000090008 。
另外,输入/输出示例 4 是一个小作业 1「N = 0”满足约束。


入力例 5

1 100
5 60
50 7 90

出力例 5

17.142857142857142349612

在这种情况下,从西端 最好在 50 米处换乘。
另外,输入/输出示例 5 是一个小作业 2「N = 0 或 给出 N = 1”满足约束。


入力例 6

4 1000
37 426
725 16 612
237 19 458
516 13 509
408 17 400

出力例 6

46.861585850556437549130

如果绝对或相对误差为 如果在 10^{-5} 范围内,则会被认为是正确的,所以 输出类似46.861585 呀 46.86159 的内容也是正确的。