分数: 600 点
问题陈述
M-kun 是一位出色的空中交通管制员。
他的雷达显示屏上,有 N 飞机编号 1, 2, ..., N,全部在同一高度飞行。
每架飞机以恒定速度飞行 0.1 每秒沿恒定方向。飞机当前坐标编号 i 是 (X_i, Y_i),飞机的方向如下:
- if U_i is
U,它飞向正方向 y 方向; - if U_i is
R,它飞向正方向 x 方向; - if U_i is
D,它飞向负数 y 方向; - if U_i is
L,它飞向负数 x 方向。
为了帮助M君的工作,判断是否有一对飞机如果继续像现在这样飞行的话会互相碰撞。
如果存在这样的一对,请找出第一次碰撞发生之前的秒数。
我们假设飞机小得可以忽略不计,因此两架飞机只有在同时到达相同坐标时才会发生碰撞。
约束
- 1 \leq N \leq 200000
- 0 \leq X_i, Y_i \leq 200000
- U_i is
U,R,D,或L. - 的当前位置 N 飞机, (X_i, Y_i),都是不同的。
- N, X_i,和 Y_i 是整数。
输入
输入由标准输入按以下格式给出:
N X_1 Y_1 U_1 X_2 Y_2 U_2 X_3 Y_3 U_3 : X_N Y_N U_N
输出
如果有一对飞机如果继续像现在一样飞行,将会相互碰撞,则打印一个整数,表示第一次碰撞发生后的秒数。
如果没有这样的对,则打印 SAFE.
示例输入 1
2 11 1 U 11 47 D
示例输出 1
230
如果飞机继续像现在一样飞行,两架飞机编号为 1 和 2 将到达坐标 (11, 24) 同时碰撞。
示例输入 2
4 20 30 U 30 20 R 20 10 D 10 20 L
示例输出 2
SAFE
没有两架飞机会相撞。
示例输入 3
8 168 224 U 130 175 R 111 198 D 121 188 L 201 116 U 112 121 R 145 239 D 185 107 L
示例输出 3
100