Description

在任何乐队中，鼓手都扮演着极其重要的角色——负责保持节奏。如果鼓手的节奏不稳定，可能会毁掉整场演出。

你是一支极受欢迎的摇滚乐队的主唱，而你现在遇到了一个小麻烦。你的鼓手刚刚辞职，去做职业电子游戏玩家了。你必须立刻找到新的鼓手。幸运的是，候选人并不缺乏，每个人都想加入你的乐队。你的任务是从中选出节奏最稳定的那个人。

你的计划如下：你会让每个候选人单独试音。在试音时，候选人会用鼓槌敲击鼓面若干次。理想情况下，相邻两次敲击之间的时间间隔应该完全相同，从而形成完美的节奏。在完美节奏中，敲击的时间戳应当呈如下等差数列：$T_0$，$T_0 + K$，$T_0 + 2\times K$，$\dots$，$T_0 + (N - 1)\times K$。

当然，在现实生活中，人类几乎不可能打出完全完美的节奏。因此，每个候选人的节奏都会有一个误差 $E$，即每个 $T_i$ 与某个完美节奏的时间戳最多相差 $E$。现在，给定一个候选人的敲击时间序列，请你求出所有可能的完美节奏中，误差 $E$ 的最小值。

Input Format

第一行为测试用例数 $T$。接下来有 $T$ 个测试用例。每个测试用例包含两行，代表一位候选人的试音。第一行为一个整数 $N$。第二行为 $N$ 个用空格分隔的整数，表示候选人每次敲击的时间戳（单位为毫秒），按递增顺序给出。

Output Format

对于每个测试用例，输出一行 "Case #x: E"，其中 $x$ 为测试用例编号（从 1 开始），$E$ 为所有可能的误差中的最小值。

只要你的答案与正确答案的绝对误差或相对误差不超过 $10^{-6}$，就会被判为正确。

3
2
10 70
4
0 10 19 30
6
2 5 10 15 20 24

Case #1: 0
Case #2: 0.5
Case #3: 0.75

Hint

限制条件

• $1 \leq T \leq 100$

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

• 时间限制：60 6 秒
• $2 \leq N \leq 10$
• $0 \leq T_i \leq 100$

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

• 时间限制：120 12 秒
• 90% 的测试点满足 $2 \leq N \leq 1000$
• 所有测试点满足 $2 \leq N \leq 50000$
• $0 \leq T_i \leq 10^6$

翻译由 ChatGPT-4.1 完成。