식물에 물 주기

온실에는 물을 주어야 하는 여러 식물이 있다.

각 식물은 원 모양의 영역을 차지한다. 어떤 두 식물도 서로 겹치거나 맞닿지 않는다.

스프링클러 두 개를 살 예정이다. 각 스프링클러는 반지름이 R인 원 안의 모든 곳에 물을 뿌린다.

스프링클러 중 하나는 아침에 작동하고, 하나는 밤에 작동한다. 식물이 충분한 물을 받았다고 만족하려면, 식물의 전체 영역이 아침에 물을 받거나 식물의 전체 영역이 밤에 물을 받아야 한다. 따라서 식물을 나타내는 각 원은 스프링클러가 물을 줄 수 있는 영역을 나타내는 두 원 중 하나 또는 둘 모두에 완전히 포함되어야 한다.

각 식물의 위치와 반지름이 주어질 때, 모든 식물에 물을 줄 수 있도록 두 스프링클러를 배치할 수 있는 최소 반지름 R을 구한다. 스프링클러는 천장에 설치되므로 스프링클러의 위치가 식물의 영역 안에 있어도 된다.

제한

메모리 제한: 1 GB. 입력 파일의 모든 수는 정수이다. 1 ≤ X ≤ 1000 1 ≤ Y ≤ 1000 1 ≤ R ≤ 100

작은 입력

시간 제한: 30초. 1 ≤ C ≤ 10 1 ≤ N ≤ 3

큰 입력

시간 제한: 60초. 1 ≤ C ≤ 30 1 ≤ N ≤ 40

• 입력 파일의 테스트 케이스 수인 정수 C가 한 줄에 주어진다. 각 테스트 케이스마다 다음 내용이 주어진다.

• 가지고 있는 식물의 수 N이 한 줄에 주어진다.

• 각 식물마다 한 줄씩, 세 정수 "X Y R"가 주어지는 N개의 줄이 이어진다. 여기서 (X, Y)는 식물 중심의 좌표이고, R은 식물의 반지름이다.

각 테스트 케이스마다 다음을 출력한다.

• 문자열 "Case #x: R"을 한 줄에 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, R은 스프링클러의 최소 반지름이다. 절대 오차 또는 상대 오차가 최대 10^{-5}인 답은 정답으로 인정된다.

첫 번째 경우에는 (20,15)를 중심으로 하는 반지름이 적어도 7인 스프링클러가 처음 두 식물에 물을 줄 수 있다. 반지름이 적어도 3인 스프링클러가 (40,10)에 있는 식물에 물을 줄 수 있다.

두 번째 경우에는 두 스프링클러 중 하나의 반지름이 적어도 8여야 한다. (30,10)에 있는 식물은 두 스프링클러 중 하나에 완전히 덮여야 한다는 점에 유의한다.