시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 15 7 7 63.636%

문제

2차원 평면 위에 N개의 점들이 찍혀 있다. 우리는 아래의 조건을 만족하도록 몇 개의 점을 고르려고 한다.

(조건 1) 적어도 세 점 이상은 골라야 한다.

(조건 2) 고른 점들 중에서 어떤 두 점을 임의로 선택해도, 선택한 두 점을 잇는 직선을 만들었을 때 이 직선을 통과하는 다른 점이 적어도 한 개 이상은 있어야 한다.

(조건 3) 최대한 많은 점을 골라야 한다.

모든 점의 좌표가 주어졌을 때, 조건을 만족하도록 점을 골라 주는 프로램을 작성하시오.

입력

첫째 줄에 점의 개수 N(3≤N≤1,000)이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 점의 x좌표와 y좌표를 나타내는 두 정수가 순서대로 주어진다. 주어지는 모든 좌표는 절대값이 10,000을 넘지 않는 정수이다. 주어지는 모든 점은 서로 다르다.

출력

첫째 줄에 고른 점들의 최대 개수를 출력한다. 점들을 고르는 것이 불가능한 경우 -1을 출력한다.

예제 입력

3
0 0
1 0
0 1

예제 출력

-1

힌트

출처

  • 문제를 번역한 사람: author5