← 返回题目列表

AtCoder · m_solutions2020_f

F. 航空安全

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

分数: 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