점 고르기

시간 제한2초메모리 제한128 MB

문제

2차원 평면 위에 서로 다른 N개의 점이 있다. 이 점들 중 일부를 골라 다음 조건을 만족시키려고 한다.

  1. 고른 점은 3개 이상이어야 한다.
  2. 고른 점 중 임의의 두 점을 잇는 직선을 생각할 때, 그 직선 위에는 두 점 외의 고른 점이 적어도 하나 더 있어야 한다.
  3. 조건을 만족하는 점의 개수를 최대화해야 한다.

모든 점의 좌표가 주어졌을 때, 조건을 만족하도록 고를 수 있는 점의 최대 개수를 구하라.

입력

첫째 줄에 점의 개수 N(3 <= N <= 1,000)이 주어진다.

둘째 줄부터 N개의 줄에는 각 점의 x좌표와 y좌표를 나타내는 두 정수가 주어진다. 모든 좌표의 절댓값은 20,000을 넘지 않는다. 주어지는 점들은 모두 서로 다르다.

출력

조건을 만족하도록 고를 수 있는 점의 최대 개수를 출력한다. 조건을 만족하는 선택이 불가능하면 -1을 출력한다.