아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

공원점

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

요약
점이 최대 100개인 각 테스트 케이스에서 한 원 위에 놓이는 가장 큰 부분집합의 크기를 구해 출력한다.
난이도

보통10점 중 7점

유형
기하, 해시맵, 조합론, 완전 탐색
정답자
아직 제출이 없습니다

문제

공선점(collinear points)은 한 직선 위에 놓인 점들의 집합이다. 이와 비슷하게, 공원점(cocircular points)은 한 원 위에 놓인 점들의 집합으로 정의할 수 있다.

점들의 집합이 주어졌을 때, 그 부분집합 가운데 모든 점이 하나의 원 위에 놓이는(즉, 공원점을 이루는) 가장 큰 부분집합의 크기를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 점의 개수 NN (1≤N≤1001 \le N \le 100)이 주어진다. 이어지는 NN개의 줄에는 각 점의 좌표 XX와 YY (−104≤X,Y≤104-10^4 \le X, Y \le 10^4)가 공백으로 구분되어 주어진다. 좌표가 완전히 같은 두 점은 존재하지 않는다.

입력의 마지막 줄에는 00이 하나 주어지며, 이는 입력의 끝을 뜻한다.

출력

각 테스트 케이스마다, 주어진 점들의 부분집합 중 하나의 원 위에 놓일 수 있는 가장 큰 부분집합의 크기를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    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