Description

Given $N$ points in the plane, some are red and the others are blue.

Find a pair of parallel lines (not necessarily parallel to the coordinate axes) such that there are no blue points between the lines, and the lines do not pass through any point. Among all such pairs, maximize the number of red points strictly between the lines. You only need to compute the number of red points that are between the chosen pair of parallel lines.

Input Format

The first line contains an integer $N$, the total number of points.

Each of the next $N$ lines contains two integers $x_i, y_i$ and a character R (red) or B (blue), specifying the point’s coordinates and color.

Output Format

Output a single integer: the number of red points.

4
0 0 R
0 1 B
1 1 R
1 0 B

2

Hint

Constraints

• For $50\%$ of the testdata, $N \le 350$.
• For $100\%$ of the testdata, $1 \le N \le 1000$, $|x_i|, |y_i| \le 10^9$, and no three points are collinear.

Notes

Translated from Croatian Highschool Competitions In Informatics 2009 Final Exam #2 T1 DVAPRAVCA.

Translated by ChatGPT 5