시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 117 11 10 8.696%

문제

공선점 (Collinear Points)은 한 직선 상에 있는 점의 집합을 말한다. 이와 비슷한게 공원점(Cocircular Points)을 한 원 위에 있는 점의 집합으로 정의할 수 있다.

점의 집합이 주어졌을 때, 이 집합의 부분 집합 중 크기가 가장 큰 공원점을 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 점의 개수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 점의 좌표 X와 Y가 주어진다. (-104 ≤ X,Y ≤ 104) 두 점의 좌표가 같은 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해, 입력으로 주어진 집합의 부분 집합 중 크기가 가장 큰 공원점의 크기를 출력한다.

예제 입력

7
-10 0
0 -10
10 0
0 10
-20 10
-10 20
-2 4
4
-10000 10000
10000 10000
10000 -10000
-10000 -9999
3
-1 0
0 0
1 0
0

예제 출력

5
3
2

힌트