빨간 점과 파란 점
시간 제한1초메모리 제한128 MB
평면 위 빨간 점과 파란 점이 주어질 때, 어떤 점도 지나지 않고 파란 점을 포함하지 않는 평행선 두 개로 감쌀 수 있는 빨간 점의 최대 개수를 구합니다.
문제
좌표평면 위에 빨간 점과 파란 점이 있다. 두 개의 서로 평행한 직선을 그어, 두 직선 사이에 엄격히 들어가는 빨간 점을 보호하려고 한다. 두 직선 사이에는 파란 점이 하나도 있으면 안 되며, 어느 직선도 점을 지나면 안 된다.
모든 빨간 점을 보호할 수 없을 수도 있다. 조건을 만족하는 두 평행선을 선택했을 때 보호할 수 있는 빨간 점의 최대 개수를 구하라.
입력
첫째 줄에 점의 개수 N이 주어진다. (1 ≤ N ≤ 1000)
다음 N개 줄에는 각 점의 x좌표, y좌표, 색상이 공백으로 구분되어 주어진다. 각 좌표는 절댓값이 10^9보다 작은 정수이고, 색상은 R 또는 B이다.
어떤 세 점도 한 직선 위에 있지 않다.
출력
조건을 만족하는 두 평행선으로 보호할 수 있는 빨간 점의 최대 개수를 출력한다.