E - 車の乗り継ぎ Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

ギガ通りは西から東へ一直線に走る，長さ L メートルの道路です．

E869120 君は最初ギガ通りの西端におり，分速 V_S メートルで残り D_S メートル走れる車に乗っています．

この通りにはこれ以外にも N 個の車があります．i 個目の車は西端から X_i メートルの位置にあり，分速 V_i メートルで残り D_i メートル走れます．

あなたは，車を 西から東の向きに 運転し，ギガ通りの東端にたどり着きたいです．

彼は，途中で車が停まっている場所まで運転してその車に乗り換えることもできます．乗り継ぎにかかる時間は 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

出力

ギガ通りの東端に何をやってもたどり着けないならば impossible と出力してください．
たどり着ける場合は，その際にかかる最短時間 (分) を出力してください．これは小数点以下何桁でも出力して良いですが，答えとの誤差（絶対誤差または相対誤差）が 10^{-5} 以内であったときのみ正解とみなされます．

入力例 1

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

出力例 1

4.000000000000000000000

次のような移動をすると 4 分でギガ通りの東端にたどり着くことができ、これが最短です。

  • まず、最初に乗る車で西端から 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 分でギガ通りの東端にたどり着くことができ、これが最短です。

  • まず、最初に乗る車で西端から 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

この場合、どうやってもギガ通りの東端にたどり着くことはできません。
また、入出力例 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 などと出力しても正解となります。