Description

你将得到一组整数坐标的点集。你的任务是计算，从这些点中选取三个互不相同的点作为顶点，能够构成的三角形的最小周长。

Input Format

输入的第一行为一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试数据。每组测试数据的第一行为一个整数 $n$，表示点的数量。接下来的 $n$ 行，每行包含两个整数 $x_i$、$y_i$，表示第 $i$ 个点的坐标。不会有两个点的坐标完全相同。

Output Format

对于每组测试数据，输出一行：

Case #$X$: $Y$

其中 $X$ 是测试用例编号，$Y$ 是最小周长。只要你的答案的绝对误差或相对误差不超过 $10^{-5}$，就会被认为是正确答案。退化三角形（即面积为零的三角形）也是允许的。

1
10
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9

Case #1: 5.656854

Hint

限制条件

• $1 \leq T \leq 15$
• $0 \leq x_i, y_i \leq 10^9$

小数据集（5 分）

• 时间限制：15 秒
• $3 \leq n \leq 10000$

大数据集（15 分）

• 时间限制：30 秒
• $3 \leq n \leq 1000000$

翻译由 ChatGPT-4.1 完成。