파티 장소

면접 대비

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

요약

한 변이 50km인 정사각형 도시에 최대 200채의 집 좌표가 주어질 때, 반지름 2.5km 안에 가장 많은 집이 들어오는 파티 장소를 찾아 그 집의 수를 구한다.

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

문제

프로그래밍 대회가 끝나면 모든 참가자가 파티를 열고 싶어 합니다. 하지만 파티가 끝나면 시간이 늦어, 참가자들은 너무 지쳐서 먼 길을 걷지 못합니다. 구체적으로, 각 참가자는 파티 장소가 자신의 집에서 2.5 km보다 멀면 참석하지 않습니다(정확히 2.5 km는 참석합니다).

따라서 가능한 한 많은 참가자의 집과 가까운 곳에서 파티를 열어야 합니다. 여러분이 할 일은 최대한 많은 참가자가 참석할 수 있도록 파티의 최적 위치를 정하는 것입니다.

도시는 한 변이 50 km인 정사각형 평면이라고 가정합니다. 참가자는 파티 장소에서 자신의 집까지 직선으로 곧장 걸어갈 수 있습니다(장애물은 없습니다).

입력

입력은 여러 줄로 이루어지며, 각 줄에는 한 참가자의 집의 $(x, y)$ 좌표를 나타내는 두 실수가 주어집니다. 각 좌표는 $0.0$ 이상 $50.0$ 이하이며(단위: km), 소수점 아래 최대 4자리까지 주어집니다. 모든 집의 위치는 서로 다릅니다. 참가자는 최대 200명입니다. 입력은 파일의 끝까지 읽습니다.

출력

파티에 참석할 수 있는 참가자의 최대 수를 정수 하나로 출력합니다.

예제2

예제 1

입력

4.0 4.0
4.0 5.0
5.0 6.0
1.0 20.0
1.0 21.0
1.0 22.0
1.0 25.0
1.0 26.0

예상 출력

예제 2
입력
```
10.0 10.0
```
예상 출력
```
1
```