Dva pravca
There are points in the plane, some red some blue. The points lived in harmony for years, until the blue points went bonkers and started attacking red points. To protect themselves, the red points decided to erect two parallel lines such that no blue points are contained between the lines. All red points between the lines will be protected by them. Lines may not pass through any points, red or blue. The red points observed that, unfortunately, not all of them can be saved in this way. Determine the largest number of red points that can be saved.
InputThe first line contains an integer N (1 ≤ N ≤ 1000), the number of points in the plane. Each of the following N lines contains the coordinates of one point and its colour. Coordinates are pairs of integers less than \mathbf{10^{9}} (one billion) in absolute value; the colour is 'R' or 'B'. No three points will be collinear.
OutputOutput the largest number of red points that can be protected by two parallel lines.
input
4
0 0 R
0 1 B
1 1 R
1 0 B
output
2 Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.