멀티킬
시간 제한2초메모리 제한128 MB
평면 위 임의의 점을 폭발점으로 정해 반경 R 안에 들어오는 좀비가 가장 많아지는 수를 그룹마다 출력합니다.
문제
좀비 사태가 시작됐다. 좀비는 쉽게 쓰러지지만 탄약이 부족해서 한 발도 허투루 쓸 수 없다. 가장 강력한 방어 무기는 멀리 떨어진 좀비까지 찾아내는 자동 유탄 발사기다. 남은 일은 한 발로 최대한 많은 좀비를 잡도록 폭발 지점을 정하는 코드를 짜는 것이다.
좀비 무리마다 살상 반경과 무리에 속한 좀비의 위치가 주어진다. 폭발 지점을 하나 골라서 한 발로 없앨 수 있는 좀비 수의 최댓값을 구하라. 좀비는 폭발 지점까지의 거리가 살상 반경 이하이면 죽는다. 폭발 지점은 평면 위 어느 좌표라도 될 수 있고 좀비가 서 있는 자리로 제한되지 않는다.
입력
첫 줄에 무리의 수 가 주어진다 ().
각 무리의 첫 줄에는 살상 반경 과 좀비 수 이 주어진다. 은 인 실수이고, 은 인 정수다. 이어지는 개 줄에는 좀비 한 마리의 좌표 와 가 주어진다 (). 반경과 좌표의 단위는 모두 미터이고, 둘 다 소수점이 붙을 수 있다.
C
R N
X1 Y1
...
XN YN
출력
각 무리마다 한 발로 없앨 수 있는 좀비 수의 최댓값을 한 줄에 하나씩 출력한다.