P13449 [GCJ 2009 Finals] Min Perimeter

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

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

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

**限制条件** - $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 完成。