P13032 [GCJ 2021 #1C] Closest Pick

你正在参加一场抽奖活动，奖品是终身免费煎饼。已有 $\textbf{N}$ 张彩票售出。每张彩票包含一个 $1$ 到 $\textbf{K}$ 之间的整数（含端点）。不同的彩票可以包含相同的整数。你确切知道所有已售出彩票上的数字，并希望通过购买两张彩票（可以包含相同的整数）来最大化中奖概率。你可以自由选择 $1$ 到 $\textbf{K}$ 之间的任意整数作为这两张彩票的数字。  你知道自己是最后一位顾客，因此在你购买彩票后，不会再有任何彩票售出。接着，系统会均匀随机选择一个 $1$ 到 $\textbf{K}$ 之间的整数 $c$（含端点）。如果满足以下条件之一，你将赢得抽奖： - 你的一张彩票到 $c$ 的距离严格小于其他所有彩票； - 你的两张彩票到 $c$ 的距离相同，且严格小于其他所有彩票。 否则，你将不会赢得抽奖。 给定已售出的 $\textbf{N}$ 张彩票上的整数，通过最优选择你的两张彩票上的整数，你能够达到的最大中奖概率是多少？

输入的第一行包含测试用例的数量 $\textbf{T}$。随后是 $\textbf{T}$ 个测试用例。每个测试用例包含两行：第一行是两个整数 $\textbf{N}$ 和 $\textbf{K}$，分别表示已售出的彩票数量和可选整数的上限；第二行包含 $\textbf{N}$ 个整数 $\textbf{P}_1, \textbf{P}_2, \ldots, \textbf{P}_\textbf{N}$，表示已售出彩票上的整数。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你通过最优选择彩票能够达到的最大中奖概率。$y$ 的答案将被认为是正确的，如果其绝对误差或相对误差不超过 $10^{-6}$。关于误差范围的解释及可接受的实数格式，请参考 FAQ。

**样例解释** 在样例 #1 中，你可以购买数字为 $4$ 和 $8$ 的彩票。当 $c$ 为 $4$、$5$、$8$、$9$ 或 $10$ 时，你将赢得抽奖，中奖概率为 $\frac{5}{10} = 0.5$。购买数字为 $6$ 和 $8$ 的彩票也能达到 $0.5$ 的中奖概率，但没有其他组合能超过这一概率。 在样例 #2 中，$6$ 和 $8$ 是一个可能的最优组合，当 $c$ 为 $6$、$8$、$9$ 或 $10$ 时，你将赢得抽奖。注意，已售出彩票上的数字不一定按升序排列。 在样例 #3 中，所有可能的 $c$ 都与至少一张已售出的彩票距离为 $0$，因此无论你如何选择彩票，都无法赢得抽奖。 在样例 #4 中，如果你至少选择一张数字为 $3$ 的彩票，你将在 $c = 3$ 时赢得抽奖，中奖概率为 $\frac{1}{4} = 0.25$。对于其他整数 $c$，你无法获胜，因此这是你能达到的最佳概率。 **数据范围** - $1 \leq \textbf{T} \leq 100$。 - $1 \leq \textbf{N} \leq 30$。 - 对于所有 $i$，$1 \leq \textbf{P}_i \leq \textbf{K}$。 **测试集 1（9 分，可见判定）** - $1 \leq \textbf{K} \leq 30$。 **测试集 2（16 分，可见判定）** - $1 \leq \textbf{K} \leq 10^9$。 翻译由 DeepSeek V3 完成