题目描述

Alice 试图阻止危险的黑洞威胁地球。目前，有三个黑洞，它们是三维空间中的不同点。Alice 将恰好创建三个大小相同的包围球体，所有三个球体必须具有相同的半径。球体之间互不干扰，因此它们可以重叠。

Alice 必须放置这些球体，使得每个黑洞至少被一个球体覆盖。此外，为了确保稳定性，被至少一个球体覆盖的所有点构成的集合必须形成一个单一连通区域。

Alice 希望尽可能低成本地解决这个关键问题。她能使用的最小半径是多少？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。每个测试用例由三行组成。第 $i$ 行包含三个整数 $X_i$、$Y_i$ 和 $Z_i$，表示第 $i$ 个黑洞的三维坐标。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个有理数，表示 Alice 解决问题所需的最小半径。如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

4
0 0 0
1 0 0
-1 0 0
4 0 0
5 0 0
-2 0 0
0 0 0
1 1 1
-1 -1 -1
-4 2 -2
5 1 -4
0 4 -9

Case #1: 0.3333333333
Case #2: 1.1666666667
Case #3: 0.5773502692
Case #4: 2.1373179212

提示

请注意，最后两个样例不会出现在小数据集中。

在样例 #1 中，我们能使用的最小半径为 $1/3$。三个球体的球心应分别位于 $(-2/3, 0, 0)$、$(0, 0, 0)$ 和 $(2/3, 0, 0)$。

限制条件

对于所有 $i$，$-1000 \le X_i \le 1000$。

对于所有 $j \ne k$，$(X_j, Y_j, Z_j) \ne (X_k, Y_k, Z_k)$。（任意两个点的坐标均不同。）

小数据集（测试集 1 – 可见）

对于所有 $i$，$Y_i = 0$。

对于所有 $i$，$Z_i = 0$。

大数据集（测试集 2 – 隐藏）

对于所有 $i$，$-1000 \le Y_i \le 1000$。

对于所有 $i$，$-1000 \le Z_i \le 1000$。

翻译由 DeepSeek V4 Pro 完成