BOJ 14605 Over Fitting (Large)

문제 링크:

문제 내용

2차원 평면에 $n$개의 점이 주어집니다. 직선을 하나 그어서 라벨이 LOVELYZ인 점들과 아닌 점들을 나누려고 합니다. 한쪽 영역에 LOVELYZ가 아닌 모든 점들을 넣어야 한다고 할 때, 반대쪽 영역에 넣을 수 있는 LOVELYZ 점의 개수의 최댓값을 구하세요.

입력

첫 줄에 점의 개수 $n$이 주어집니다. ($6 \le n \le 5000$)

다음 $n$줄에 걸쳐서 $n$개의 점의 정보가 한 줄에 하나씩 주어집니다. 하나의 점의 정보는 $x$좌표, $y$좌표, 라벨 순으로 주어집니다. ($-10^9 \le x, y \le 10^9$, 라벨의 길이는 15 이하이며 영어 대문자로만 이루어져 있음)

라벨이 LOVELYZ인 점과 아닌 점은 각각 3개 이상씩 존재하며, 세 점이 한 직선 위에 놓이는 경우는 없습니다.

출력

문제의 정답을 출력합니다.

문제 풀이