配点: 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
- 输入全部为整数
部分点
该问题分为多个子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。
- (9 点) N = 0
- (6 点) N = 0 或 给出 N = 1
- (22 点) N \leq 10
- (30 点) V_S = 1 和所有 对于 i 反对 V_i = 1
- (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 的内容也是正确的。