← 返回题目列表

AtCoder · cf_2015_morning_hard_h

D. 阿林科

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

問題文

林戈踩着无限长的棍子行走 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