Trong nhà kính của bạn có một số cây cần được tưới nước.

Mỗi cây chiếm một diện tích là một hình tròn. Không có hai cây nào nằm đè lên nhau hoặc chạm nhau.

Bạn định mua hai vòi phun nước. Mỗi vòi phun sẽ phun nước cho mọi thứ trong một hình tròn bán kính \(R\).

Một vòi phun sẽ hoạt động vào buổi sáng, và vòi kia sẽ hoạt động vào ban đêm. Để bạn hài lòng rằng một cây sẽ nhận đủ nước, toàn bộ diện tích của cây đó phải được tưới vào buổi sáng, hoặc toàn bộ diện tích của cây đó phải được tưới vào ban đêm. Vì vậy, mỗi hình tròn đại diện cho một cây phải nằm hoàn toàn trong một hoặc cả hai hình tròn đại diện cho khu vực mà vòi phun có thể tưới.

Cho biết vị trí và bán kính của mỗi cây, hãy tìm bán kính \(R\) nhỏ nhất để có thể đặt hai vòi phun tưới được tất cả các cây. Các vòi phun sẽ được lắp trên trần nhà, vì vậy vị trí của vòi phun có thể nằm bên trong diện tích của một cây.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(C\), số lượng bộ dữ liệu trong file input.
  Với mỗi bộ dữ liệu:
• Một dòng chứa \(N\), trong đó \(N\) là số lượng cây bạn có.
• \(N\) dòng, mỗi dòng cho một cây, chứa ba số nguyên $X$ $Y$ $R$, trong đó (\(X\), \(Y\)) là tọa độ tâm của cây, và \(R\) là bán kính của cây.

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Một dòng chứa chuỗi Case #x: R trong đó \(x\) là số thứ tự của bộ dữ liệu, bắt đầu từ 1, và \(R\) là bán kính nhỏ nhất của vòi phun.

Bất kỳ câu trả lời nào có sai số tuyệt đối hoặc tương đối không quá \(10^{-5}\) đều sẽ được chấp nhận.

Ràng buộc

• Tất cả các số trong file input là số nguyên.
• \(1 \le X \le 1000\)
• \(1 \le Y \le 1000\)
• \(1 \le R \le 100\)

Phân nhóm

• Small Input: \(1 \le C \le 10, 1 \le N \le 3\).
• Large Input: \(1 \le C \le 30, 1 \le N \le 40\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3
20 10 2
20 20 2
40 10 3
3
20 10 3
30 10 3
40 10 3

Case #1: 7.000000
Case #2: 8.000000

Nguồn

Google Code Jam 2009, Vòng 2, bài Watering Plants.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.