AT_gigacode_2019_e 車の乗り継ぎ

[problemUrl]: https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_e ギガ通りは西から東へ一直線に走る，長さ $ L $ メートルの道路です． E869120 君は最初ギガ通りの西端におり，分速 $ V_S $ メートルで残り $ D_S $ メートル走れる車に乗っています． この通りにはこれ以外にも $ N $ 個の車があります．$ i $ 個目の車は西端から $ X_i $ メートルの位置にあり，分速 $ V_i $ メートルで残り $ D_i $ メートル走れます． あなたは，車を **西から東の向きに** 運転し，ギガ通りの東端にたどり着きたいです． 彼は，途中で車が停まっている場所まで運転してその車に乗り換えることもできます．乗り継ぎにかかる時間は $ 0 $ 分として良いです． さて，彼はギガ通りの東端にたどり着けるでしょうか？たどり着けない場合このことを報告し，たどり着ける場合は東端にたどり着くのに必要な最短時間 (分) を報告してください．

N/A

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

### 制約 - $ 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 $ に取り掛かる人は，このヒントも踏まえて考えてみるのも良いでしょう．** ### Sample Explanation 1 次のような移動をすると $ 4 $ 分でギガ通りの東端にたどり着くことができ、これが最短です。 - まず、最初に乗る車で西端から $ 3 $ メートルのところまで進む。これに $ 3/1\ =\ 3 $ 分かかる。 - 次に、$ 1 $ 個目の車で西端から $ 6 $ メートルのところまで進む。これに $ 3/5\ =\ 0.6 $ 分かかる。 - 最後に、$ 2 $ 個目の車で東端 (西端から $ 10 $ メートルのところ) まで進む。これに $ 4/10\ =\ 0.4 $ 分かかる。 - 合計 $ 3\ +\ 0.6\ +\ 0.4\ =\ 4 $ 分で、東端にたどり着くことができた。 ### Sample Explanation 2 次のような移動をすると $ 4.4 $ 分でギガ通りの東端にたどり着くことができ、これが最短です。 - まず、最初に乗る車で西端から $ 3 $ メートルのところまで進む。これに $ 3/1\ =\ 3 $ 分かかる。 - そして、$ 1 $ 個目の車で東端 (西端から $ 10 $ メートルのところ) まで進む。これに $ 7/5\ =\ 1.4 $ 分かかる。 - 合計 $ 3\ +\ 1.4\ =\ 4.4 $ 分で、東端にたどり着くことができた。 ### Sample Explanation 3 この場合、どうやってもギガ通りの東端にたどり着くことはできません。 また、入出力例 $ 3 $ は小課題 $ 4 $「$ V_S\ =\ 1 $、$ V_i\ =\ 1 $」の制約を満たします。 ### Sample Explanation 4 答えは `1.00009e-05` のような形式ではなく、`0.00001000090008` のような形式で出力する必要があることに注意してください。 また、入出力例 $ 4 $ は小課題 $ 1 $「$ N\ =\ 0 $」の制約を満たします。 ### Sample Explanation 5 この場合、西端から $ 50 $ メートルのところで乗り継ぐのが最適となります。 また、入出力例 $ 5 $ は小課題 $ 2 $「$ N\ =\ 0 $ または $ N\ =\ 1 $」の制約を満たします。 ### Sample Explanation 6 絶対誤差または相対誤差が $ 10^{-5} $ 以内ならば正解とみなされますので、`46.861585` や `46.86159` などと出力しても正解となります。