Air Safety

AtCoder

IDm_solutions2020_f

Time3000ms

Memory256MB

Difficulty—

M-kun is a brilliant air traffic controller. On the display of his radar, there are $N$ airplanes numbered $1, 2, ..., N$, all flying at the same altitude. Each of the airplanes flies at a constant speed of $0.1$ per second in a constant direction. The current coordinates of the airplane numbered $i$ are $(X_i, Y_i)$, and the direction of the airplane is as follows: * if $U_i$ is `U`, it flies in the positive $y$ direction; * if $U_i$ is `R`, it flies in the positive $x$ direction; * if $U_i$ is `D`, it flies in the negative $y$ direction; * if $U_i$ is `L`, it flies in the negative $x$ direction. To help M-kun in his work, determine whether there is a pair of airplanes that will collide with each other if they keep flying as they are now. If there is such a pair, find the number of seconds after which the first collision will happen. We assume that the airplanes are negligibly small so that two airplanes only collide when they reach the same coordinates simultaneously. ## Constraints * $1 \leq N \leq 200000$ * $0 \leq X_i, Y_i \leq 200000$ * $U_i$ is `U`, `R`, `D`, or `L`. * The current positions of the $N$ airplanes, $(X_i, Y_i)$, are all distinct. * $N$, $X_i$, and $Y_i$ are integers. ## Input Input is given from Standard Input in the following format: $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$ [samples]

Samples

Input #1

2
11 1 U
11 47 D

Output #1

230

If the airplanes keep flying as they are now, two airplanes numbered $1$ and $2$ will reach the coordinates $(11, 24)$ simultaneously and collide.

Input #2

Output #2

SAFE

No pair of airplanes will collide.

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Air Safety",
    "description": {
      "content": "M-kun is a brilliant air traffic controller. On the display of his radar, there are $N$ airplanes numbered $1, 2, ..., N$, all flying at the same altitude.   Each of the airplanes flies at a constant ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "m_solutions2020_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "M-kun is a brilliant air traffic controller.\nOn the display of his radar, there are $N$ airplanes numbered $1, 2, ..., N$, all flying at the same altitude.  \nEach of the airplanes flies at a constant ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments