아마추어 무선 네트워크

무선 송수신 채널 협회(SWERC)는 허츠빌에 사는 사람들로 이루어진 작은 모임이다. 이들은 전파를 이용한 잡담 모임을 열기를 좋아한다. SWERC에는 모든 회원이 사용하는 공식 무선 주파수가 하나 있고, 모든 회원은 협회의 다른 모든 송신기에 도달할 수 있는 매우 강력한 송신기를 가지고 있어서 다 같이 즐겁게 이야기할 수 있다. 이들이 대화할 때마다 각 송신기는 SWERC 회원들이 사용하는 다른 송신기까지의 거리에 따라 방출 전력을 자동으로 설정한다. 구체적으로, 각 회원의 송신기 전력은 가장 먼 송신기까지의 거리에 비례한다.

불행히도 이들에게는 허츠빌의 새 시장이 통신을 좋아하지 않는다. 정확히 말하자면, 시장은 송신기의 전력이 너무 세서 SWERC의 무선 통신이 공중 보건에 위험하다고 주장한다. 시장이 걱정하는 것은 SWERC 송신기의 최대 전력 설정이다.

협상을 시도하기 위해 SWERC는 두 그룹으로 나뉘어 각 그룹이 별도의 무선 주파수를 사용하려 한다. 그러면 각 그룹의 송신기는 같은 그룹의 다른 송신기와만 통신하므로 최대 송신 전력이 줄어든다. 구체적으로, SWERC는 각 회원을 두 그룹 중 하나에 배정하는 방법을 정한다. 그룹 1에서 송신기는 이전과 같이 작동한다. 각 송신기는 그룹 1에서 가장 먼 송신기까지의 거리에 따라 방출 전력을 설정하여, 그룹 1의 모든 회원이 이전처럼 계속 통신할 수 있게 한다. 그룹 2도 마찬가지다. SWERC는 매우 포용적인 모임이므로 어떤 회원도 따로 떼어 놓는 것을 고려하지 않는다. 따라서 각 그룹에는 적어도 두 명이 있어야 하며, 어느 회원도 그룹에서 혼자 남지 않는다.

SWERC는 곧 시장을 만나 구체적인 제안을 내놓아야 한다. 이들은 SWERC를 두 그룹으로 나누되 각 그룹에 적어도 두 명이 있고, 각 SWERC 회원에 대해 그 회원과 같은 그룹의 회원 사이의 최대 거리가 d 이하가 되게 하는 가장 작은 거리 d를 알아야 한다. 이들을 도와줄 수 있는가?

입력은 여러 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수를 나타내는 정수가 하나 주어진다. 각 테스트 케이스가 이어진다. 테스트 케이스의 첫 줄에는 SWERC 회원 수를 나타내는 정수 4 ≤ N ≤ 700이 하나 주어진다. 이어서 각 회원을 설명하는 N개의 줄이 주어진다. 각 줄에는 i번째 SWERC 회원의 기지국 x좌표와 y좌표를 나타내는 두 정수 −10³ ≤ Xi ≤ 10³과 −10³ ≤ Yi ≤ 10³이 공백 하나를 사이에 두고 주어진다. 두 기지국은 항상 서로 다른 위치에 있다. 즉 모든 1 ≤ i < j ≤ N에 대해 (Xi, Yi) ≠ (Xj, Yj)이다.

입력의 각 테스트 케이스에 대해, 소수점 오른쪽에 정확히 두 자리를 가진 부동소수점 수 d를 한 줄에 출력한다. d의 값은 SWERC 회원을 두 그룹으로 나누되 각 그룹에 적어도 두 명이 있고, 같은 그룹의 임의의 두 회원 사이의 유클리드 거리가 d 이하가 되게 하는 방법이 존재하도록 하는 가장 작은 값(올림)이어야 한다. 출력에 빈 줄이 있어서는 안 된다.

그림 1: 예제 입력의 해답을 나타낸 그림