Problem Description

Xiaoming is playing a war game. There are $N$ enemy units on the map, which can be seen as points on a 2D plane. For the $i$-th unit, its position at time $0$ is $(X_i, Y_i)$, its direction is $D_i$ (one of up, down, left, right, written as U/D/L/R), and its speed is $V_i$. Xiaoming’s weapon is a railgun, which can only be used once, but it is extremely powerful. Xiaoming may choose to fire the railgun at some non-negative integer time. Each shot can destroy all enemy units on a single straight line (parallel to the coordinate axes). Please compute the maximum number of enemy units Xiaoming can destroy.

Input Format

The first line contains an integer $N$. The next $N$ lines each contain $3$ integers $X_i$, $Y_i$, $V_i$, and an uppercase character $D_i$.

Output Format

Output one integer, which is the answer.

4
0 0 1 R
0 10 1 R
10 10 2 D
2 3 2 L

3

Hint

For all test cases, $1 \le N \le 1000$, $-10^6 \le X_i, Y_i \le 10^6$, $0 \le V_i \le 10^6$.

Lanqiao Cup 2019 National Contest Group A Problem H (Group C Problem J).

Translated by ChatGPT 5