AT_m_solutions2020_f Air Safety

M 君是一名出色的航空管制官。 现在，在他管理的雷达显示屏上，有编号为 $1, 2, \ldots, N$ 的 $N$ 架飞机，全部以相同的高度飞行。 每架飞机都以每秒 $0.1$ 的恒定速度，沿着固定的方向飞行。编号为 $i$ 的飞机当前坐标为 $(X_i, Y_i)$，其飞行方向如下： - 若 $U_i$ 为 `U`，则向 $y$ 坐标的正方向飞行。 - 若 $U_i$ 为 `R`，则向 $x$ 坐标的正方向飞行。 - 若 $U_i$ 为 `D`，则向 $y$ 坐标的负方向飞行。 - 若 $U_i$ 为 `L`，则向 $x$ 坐标的负方向飞行。 请帮助 M 君判断，是否存在一对飞机会在保持当前状态下发生碰撞。 如果存在，请求出最早会发生碰撞的时间（从现在起多少秒后）。 注意，所有飞机都可以视为点，只有当两架飞机同时到达同一坐标时才会发生碰撞。

输入以以下格式从标准输入读入。 > $N$ $X_1$ $Y_1$ $U_1$ $X_2$ $Y_2$ $U_2$ $X_3$ $Y_3$ $U_3$ $\ldots$ $X_N$ $Y_N$ $U_N$

如果存在会发生碰撞的飞机对，请输出最早发生碰撞的时间（从现在起多少秒后，输出整数）。 如果不存在，请输出 `SAFE`。

### 约束条件 - $1 \leq N \leq 200000$ - $0 \leq X_i, Y_i \leq 200000$ - $U_i$ 为 `U`、`R`、`D`、`L` 中的一个 - $N$ 架飞机的当前位置 $(X_i, Y_i)$ 均不相同 - $N, X_i, Y_i$ 均为整数 ### 样例解释 1 在这种情况下，$230$ 秒后，编号 $1$ 和编号 $2$ 的飞机会同时到达坐标 $(11, 24)$，并发生碰撞。 ### 样例解释 2 不存在任何会发生碰撞的飞机对。 由 ChatGPT 4.1 翻译