Gone Fishing

면접 대비

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

요약

그물 반지름과 최대 100마리 물고기 좌표가 주어질 때, 반지름 크기의 원 하나에 담을 수 있는 물고기 최대 수를 구한다.

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

문제

It is getting dark and the mosquitoes are attacking Fisherman Floyd. Floyd decides to throw his circular net one last time and wants to make the most out of the last throw.

Given the size (radius) of Floyd’s net and positions (x,y) of a set of fish, what is the maximum fish Floyd can catch with one throw? That is, find the maximum points you can have in the net (circle). If a point (fish) is within 10-6 of the circle boundary, consider the point in the circle.

입력

The first input line provides the radius of the circle. The second input line contains an integer, n (1 ≤ n ≤ 100), indicating the number of fish. Each of the next n input lines provides the location (x,y) for one fish. Assume all these points are distinct. Also assume that all the x and y values in the input (as well as the circle radius) are integers between 1 and 1000, inclusive.

출력

Print the maximum fish Floyd can catch with one throw.

예제2

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