Description

你是邪恶银河帝国的反抗者，现在正处于逃亡之中！

你已经破坏了帝国的邪恶工厂，帝国安全部队很快就会追捕你！工厂位于编号为 0 的小行星上，在一个包含 $\mathbf{N}$ 个编号小行星的系统中。你的逃生飞船 Century Quail 停靠在编号为 1 的小行星上，如果你能到达那里，就能安全逃脱。

每颗小行星在空间中是一个点，并且有自己的速度，你始终随着你当前所在的小行星一起运动。你的“小行星跳跃器”允许你在系统内任意两颗小行星间瞬间跳跃。长距离跳跃比短距离跳跃更令人恐惧（宇宙真空更让人害怕），所以你希望最小化你所需跳跃的最大距离。然而，从现在开始，如果你连续超过 $\mathbf{S}$ 秒没有跳跃，就会被帝国安全部队抓住。也就是说，从现在到第一次跳跃的间隔，以及之后每次跳跃之间的间隔，都必须小于等于 $\mathbf{S}$。你可以在任意时刻跳跃，不必等到整秒。你只要跳跃到 1 号小行星，就算逃脱成功。

第 $i$ 颗小行星在空间中的初始位置为 $(\mathbf{x}_{\mathbf{i}}, \mathbf{y}_{\mathbf{i}}, \mathbf{z}_{\mathbf{i}})$，每秒会移动 $(\mathbf{V}_{\mathbf{x i}}, \mathbf{V}_{\mathbf{y i}}, \mathbf{V}_{\mathbf{z i}})$ 的距离。小行星的运动是连续的，而不是每秒离散地更新。（也可能有静止的小行星。）即使两颗小行星在同一时刻占据同一点，也不会发生任何事。你只能通过跳跃在小行星之间移动，即便它们在你跳跃的那一刻正好重合。

在最小化最大跳跃距离的逃脱方案中，这个最大跳跃距离是多少？

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例。每组数据的第一行为两个整数：$\mathbf{N}$（小行星数量）和 $\mathbf{S}$（你最多能连续不跳跃的秒数）。接下来有 $\mathbf{N}$ 行描述小行星。第 $i$ 行（从 0 开始编号）包含 6 个整数，分别为该小行星的初始位置 $(\mathbf{x}_{\mathbf{i}}, \mathbf{y}_{\mathbf{i}}, \mathbf{z}_{\mathbf{i}})$，以及每秒移动的距离 $(\mathbf{V}_{\mathbf{x i}}, \mathbf{V}_{\mathbf{y i}}, \mathbf{V}_{\mathbf{z i}})$。

Output Format

对于每组测试用例，输出一行 Case #x: y，其中 $\mathrm{x}$ 为测试用例编号（从 1 开始），$\mathrm{y}$ 为你为逃脱所需的最大跳跃距离（浮点数）。如果 $\mathrm{y}$ 与正确答案的绝对误差或相对误差不超过 $10^{-4}$，则视为正确。

3
3 7
0 0 0 0 0 0
1 2 2 0 0 0
1 1 1 0 0 0
5 10
0 0 0 0 0 0
35 0 0 -1 0 0
1 54 0 0 -2 0
2 -150 0 0 10 0
4 0 0 -1 0 0
3 1
-10 2 0 1 0 0
0 0 10 0 0 -1
-10 -2 0 1 0 0

Case #1: 1.7320508
Case #2: 2.0000000
Case #3: 4.0000000

Hint

样例解释

样例第 1 组是唯一可能出现在小数据集中的样例。其他样例可能出现在大数据集中。

在样例第 1 组中，我们从 $(0,0,0)$ 的静止小行星出发，飞船在 $(1,2,2)$ 的小行星上。还有一颗小行星在 $(1,1,1)$。一种做法是直接跳到飞船上，距离为 3。另一种做法是先跳到另一颗小行星，距离为 $\operatorname{sqrt}(3)$，再从那里跳到飞船，距离为 $\operatorname{sqrt}(2)$。最大跳跃距离分别为 3 和 $\operatorname{sqrt}(3)$，所以第二种方案更优。

注意，小数据集中 $\mathbf{S}$ 的值无关紧要。因为所有小行星都静止，所以可以瞬间完成所有跳跃。

在样例第 2 组中，我们从 $(0,0,0)$ 的静止小行星出发。我们可以等待 4 秒直到第 4 号小行星靠近，跳到它上面，在它上面飞 1 秒，然后在第 5 秒跳回 0 号小行星（此时两者距离为 1）。然后我们在 0 号小行星上等待 10 秒，刚好不被抓住，然后在第 15 秒跳到高速移动的第 3 号小行星。两秒后，第 3 号小行星飞到第 2 号小行星附近，我们跳到第 2 号小行星。在第 27 秒时，我们可以从第 2 号小行星跳回第 0 号。我们耐心等待，直到第 35 秒第 1 号小行星到达我们这里，跳上去即可逃脱。我们跳的最长距离是第 15 秒从 0 号跳到 3 号，距离为 2。

在样例第 3 组中，安全部队非常活跃！你当然可以等 1 秒直接跳到 1 号小行星，但更优的方案是反复在 0 号和 2 号小行星之间跳跃，等待 1 号小行星靠近再跳过去，这样最长跳跃距离只有 4。

限制条件

• $1 \leqslant \mathbf{T} \leqslant 20$。
• $2 \leqslant \mathbf{N} \leqslant 1000$。
• $1 \leqslant \mathbf{S} \leqslant 100$。
• $-500 \leqslant \mathbf{x}_{\mathbf{i}} \leqslant 500$。
• $-500 \leqslant \mathbf{y}_{\mathbf{i}} \leqslant 500$。
• $-500 \leqslant \mathbf{z}_{\mathbf{i}} \leqslant 500$。

小数据集（8 分，测试集 1 - 可见）

• $\mathbf{V}_{\mathbf{x i}}=0$。
• $\mathbf{V}_{\mathbf{y i}}=0$。
• $\mathbf{V}_{\mathbf{z i}}=0$。

大数据集（17 分，测试集 2 - 隐藏）

• $-500 \leqslant \mathbf{V}_{\mathbf{x i}} \leqslant 500$。
• $-500 \leqslant \mathbf{V}_{\mathbf{y i}} \leqslant 500$。
• $-500 \leqslant \mathbf{z}_{\mathbf{i}} \leqslant 500$。

翻译由 GPT4.1 完成。