인터넷 케이블
시간 제한4초메모리 제한256 MB
직선 하나와 거리 d를 정해 주어진 점들 중 정확히 거리 d만큼 떨어진 점의 수가 최대가 되도록 할 때, 그 최댓값을 구한다.
문제
플랫랜디아에서 인기 있는 인터넷 서비스 제공업체 «조타»가 영향력을 넓히려 한다. 이를 위해 «조타»는 새 인터넷 케이블을 설치하려 한다. 인터넷 케이블은 평면 위의 직선으로 생각할 수 있다.
«조타»는 플랫랜디아에 n명의 잠재적 가입자가 있고, i번째 가입자는 좌표 (xi, yi)에 있는 집에 살며, 한 집에는 가입자가 한 명 이하로 산다는 것을 알고 있다. 인터넷 케이블은 선택한 일정 거리에 있는 모든 가입자에게 인터넷을 제공하도록 설정할 수 있다. 다시 말해, 인터넷 케이블을 거리 d로 설정하면, 가입자의 집이 있는 점에서 인터넷 케이블을 나타내는 직선까지의 데카르트 거리가 d인 가입자에게만 인터넷을 제공한다.
«조타»의 엔지니어들이 이 인터넷 케이블로 포괄되는 가입자 수가 최대가 되도록 인터넷 케이블을 설치하도록 도와라.
입력
첫째 줄에는 입력 데이터의 테스트 예시 수를 나타내는 자연수 t가 주어진다. 그다음에 테스트 설명이 이어진다.
각 테스트의 설명은 여러 줄로 이루어진다. 첫째 줄에는 가입자 수를 나타내는 정수 n (1 ≤ n ≤ 10³)이 주어진다.
다음 n개 줄에는 i번째 가입자의 좌표를 나타내는 두 정수 xi, yi (−10⁹ ≤ xi, yi ≤ 10⁹)가 주어진다. 어떤 두 가입자의 집도 같은 점에 있지 않음이 보장된다.
모든 테스트에 걸친 n의 합은 10³을 넘지 않는다.
출력
«조타»가 포괄할 수 있는 최대 가입자 수를 나타내는 정수 하나를 출력한다.