원과 점

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

요약

점이 최대 300개 주어질 때 반지름 1인 원 하나로 덮을 수 있는 점의 최대 개수를 구한다.

난이도: 보통10점 중 7점
유형: 기하, 완전 탐색, 정렬, 투 포인터
정답자: 아직 제출이 없습니다

문제

$xy$ 평면 위에 $N$ 개의 점이 있다. 반지름이 $1$ 인 원 하나로 이 점들을 최대 몇 개까지 포함할 수 있는지 구하여라. 점이 원의 내부에 있거나 원의 경계(원 위)에 있으면 그 점은 원에 포함된 것으로 본다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 점의 개수 $N$ 이 주어진다. 이어지는 $N$ 개의 줄에는 각 점의 좌표 $X$ 와 $Y$ 가 소수점 다섯째 자리까지 주어진다.

입력의 마지막 줄에는 $0$ 이 주어지며, 이 줄은 입력의 끝을 의미한다.

$1 \le N \le 300$
$0 \le X, Y \le 10.0$
서로 다른 두 점 사이의 거리가 $0.0001$ 보다 작은 경우는 없다.
두 점 사이의 거리 $d$ 가 $1.999 \le d \le 2.0001$ 을 만족하는 경우는 없다.
세 점이 반지름 $1$ 인 원 하나의 경계에 동시에 가깝게 놓이는 경우는 없다. 즉, 어떤 반지름 $1$ 인 원의 중심에서 세 점 $P_1, P_2, P_3$ 까지의 거리를 각각 $d_1, d_2, d_3$ 이라 할 때, $0.9999 \le d_i \le 1.0001$ 을 세 점이 동시에 만족하는 경우는 없다.

이러한 조건들 덕분에 어떤 점이 원의 경계에 애매하게 걸치는 상황은 발생하지 않는다.

출력

각 테스트 케이스마다, 반지름이 $1$ 인 원 하나가 포함할 수 있는 점의 최대 개수를 한 줄에 출력한다.

예제3

예제 1

입력

3
6.47634 7.69628
5.16828 4.79915
6.69533 6.20378
6
7.15296 4.08328
6.50827 2.69466
5.91219 3.86661
5.29853 4.16097
6.10838 3.46039
6.34060 2.41599
8
7.90650 4.01746
4.10998 4.18354
4.67289 4.01887
6.33885 4.28388
4.98106 3.82728
5.12379 5.16473
7.84664 4.67693
4.02776 3.87990
20
6.65128 5.47490
6.42743 6.26189
6.35864 4.61611
6.59020 4.54228
4.43967 5.70059
4.38226 5.70536
5.50755 6.18163
7.41971 6.13668
6.71936 3.04496
5.61832 4.23857
5.99424 4.29328
5.60961 4.32998
6.82242 5.79683
5.44693 3.82724
6.70906 3.65736
7.89087 5.68000
6.23300 4.59530
5.92401 4.92329
6.24168 3.81389
6.22671 3.62210
0

예상 출력

예제 2
입력
```
2
5.00000 5.00000
5.50000 5.00000
0
```
예상 출력
```
2
```
예제 3
입력
```
2
0.50000 0.50000
9.50000 9.50000
0
```
예상 출력
```
1
```