점 고르기
시간 제한2초메모리 제한128 MB
평면 위 최대 1000개의 점 중에서 선택된 두 점을 지나는 모든 직선이 항상 세 번째 선택된 점을 지나도록 하는 최대 부분집합의 크기를 구하고, 불가능하면 -1을 출력합니다.
문제
2차원 평면 위에 서로 다른 N개의 점이 있다. 이 점들 중 일부를 골라 다음 조건을 만족시키려고 한다.
- 고른 점은 3개 이상이어야 한다.
- 고른 점 중 임의의 두 점을 잇는 직선을 생각할 때, 그 직선 위에는 두 점 외의 고른 점이 적어도 하나 더 있어야 한다.
- 조건을 만족하는 점의 개수를 최대화해야 한다.
모든 점의 좌표가 주어졌을 때, 조건을 만족하도록 고를 수 있는 점의 최대 개수를 구하라.
입력
첫째 줄에 점의 개수 N(3 <= N <= 1,000)이 주어진다.
둘째 줄부터 N개의 줄에는 각 점의 x좌표와 y좌표를 나타내는 두 정수가 주어진다. 모든 좌표의 절댓값은 20,000을 넘지 않는다. 주어지는 점들은 모두 서로 다르다.
출력
조건을 만족하도록 고를 수 있는 점의 최대 개수를 출력한다. 조건을 만족하는 선택이 불가능하면 -1을 출력한다.