D - ありんこ
解説
/
実行時間制限: 4 sec / メモリ制限: 256 MB
問題文
りんごさんは無限に長い棒の上を歩く N 匹のアリを眺めています。今、i 匹目のアリは座標 X_i の場所にいて、速度 S_i で方向 D_i を向いて歩いています。D_i が R
のときは座標が増加する向き、D_i が L
のときは座標が減少する向きを表します。
りんごさんは K 匹のアリを棒から取り除くことができます。このとき、はじめにアリどうしが衝突するまでの時間の最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N K X_1 S_1 D_1 X_2 S_2 D_2 : X_N S_N D_N
- 1 行目には、2 つの整数 N (2 ≦ N ≦ 10^5), K (1 ≦ K ≦ N-1) が空白区切りで与えられる。これは、アリが N 匹、りんごさんが取り除くことのできるアリが K 匹であることを表す。
- 2 行目からの N 行には、アリの情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、整数 X_i (0 ≦ X_i ≦ 10^9), S_i (1 ≦ S_i ≦ 10^6) と文字 D_i (D_i は
L
またはR
) が与えられる。これは、i 匹目のアリがはじめ座標 X_i にいて、速度 S_i で方向 D_i を向いて歩くことを表す。ただし、X_i は全て相異なることが保証される。
出力
はじめにアリどうしが衝突するまでの時間の最大値を 1 行に出力せよ。出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容される。アリどうしが衝突しないようにすることができる場合は、代わりに Infinity
と出力せよ。出力の末尾に改行を入れること。
入力例1
3 1 4 2 R 7 1 L 0 4 R
出力例1
2.000000000000000
2 匹目のアリを取り除いたとき、はじめにアリどうしが衝突するまでの時間が最も長くなります。
入力例2
7 2 1 3 L 2 3 R 3 2 L 4 2 L 5 4 R 6 5 L 9 1 R
出力例2
1.333333333333333
小数点以下は何桁出力してもかまいません。
入力例3
2 1 0 1000000 R 1000000000 1000000 R
出力例3
Infinity