마지막 그물 던지기

면접 대비

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

요약

반지름 R인 그물과 n마리 물고기의 좌표가 주어질 때, 반지름 R인 원 하나에 들어가는 물고기의 최대 수를 구합니다.

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

문제

모기떼가 달려드는 저녁, 낚시꾼 플로이드는 원형 그물을 마지막으로 한 번 던지려 한다. 그물의 반지름과 물고기들의 위치 $(x, y)$ 가 주어진다. 플로이드가 그물을 한 번 던져 잡을 수 있는 물고기의 최대 수를 구하라. 즉 원 안에 들어가는 점의 최대 개수를 구한다. 점이 원의 경계로부터 $10^{-6}$ 이내에 있으면 원 안에 있는 것으로 본다.

입력

첫 줄에 그물의 반지름이 주어진다. 둘째 줄에는 물고기의 수 $n$ ( $1 ≤ n ≤ 100$ )이 주어진다. 이어서 $n$ 개의 줄에 각 물고기의 위치 $(x, y)$ 가 한 줄에 하나씩 주어진다. 모든 점은 서로 다르다. 입력의 모든 $x$ , $y$ 값과 반지름은 1 이상 1000 이하의 정수다.

출력

플로이드가 그물을 한 번 던져 잡을 수 있는 물고기의 최대 수를 출력한다.

예제2

예제 1
입력
```
20
4
6 7
5 5
190 100
4 4
```
예상 출력
```
3
```
예제 2
입력
```
3
2
1 1
95 4
```
예상 출력
```
1
```