P15242 [NHSPC 2025] 神圣的连线仪式

在遥远的「坐标王国」里，大地上散落着 $n$ 个祭坛。这些祭坛是王国与诸神沟通的媒介，每一个祭坛都有自己的名字与位置，而它们的位置总是整齐地记录在平面坐标上，永不重复，依序分别为 $(x_1 , y_1 ), (x_2 , y_2 ), \dots , (x_n , y_n )$。 每逢百年一度的「能量苏醒节」，国王必须召集全国祭司，在大地上进行一场庄严神圣的连线仪式。传说中，当某些祭坛之间以神圣的光束相连，能量就会在它们之间流动，进而唤醒沉睡的巨龙与大地之灵，守护整个王国。然而，仪式并不能随意进行。祭司必须遵循古老的规则： 1. 仪式中必须选出 $k$ 条连线，其中 $k$ 的值介于 $1$ 到 $18$ 之间。 2. 每条连线都必须连接两个不同的祭坛。 3. 任何一个祭坛在整个仪式中至多只能参与一条连线，也就是说，所有连线的端点必须互不重复。 4. 任两条连线不可在平面上交叉或重叠，否则会彼此干扰。 能量的流动并非毫无代价。两个祭坛之间的连线会消耗祭司们的法力，而法力的消耗量与它们的距离成正比，而第 $i$ 个祭坛与第 $j$ 个祭坛，即位置 $(x_i , y_i )$ 与位置 $(x_j , y_j )$，之间的距离的定义是欧几里得距离： $$ \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} $$ 因此，如果选出的连线过长，对祭司们将会是沉重的负担，如果法力不足，将会导致连线仪式无法完成。反之，如果能找到合适的祭坛，使得总连线距离最短，那么仪式就能以最小的法力消耗完成，并且释放出最大的能量。 作为王国的御用解题大师，你肩负重责大任。国王将祭坛的坐标交给你，并要求你算出最小的总法力消耗。为了方便起见，我们采用连线的总长度来代表祭司们法力的总消耗量。你的答案将直接决定仪式能否顺利完成，甚至影响王国的存亡。

$$ \begin{aligned} &n \; k \\ &x_1 \; y_1 \\ &x_2 \; y_2 \\ &\vdots \\ &x_n \; y_n \end{aligned} $$ - $n$ 为祭坛数量。 - $k$ 为需要选出的连线数量。 - $x_i,y_i$ 代表第 $i$ 个祭坛的坐标是 $(x_i,y_i)$。

$$a$$ - $a$ 代表最小的总法力消耗。相对误差或绝对误差在 $10^{-6}$ 以下均视为正确。也就是说，若正确答案是 $b$，则你的答案只要满足 $$ \frac{\lvert a - b \rvert}{\max(\lvert a \rvert, \lvert b \rvert, 1)} \leq 10^{-6} $$ 即会被视为正确。

### 数据限制 - $1 \leq k \leq 18$。 - $2k \leq n \leq 10^5$。 - $0 \leq x_i, y_i \leq 10^9$。 - 所有祭坛坐标均不同。 - 输入的数皆为整数。 ### 评分说明 本题共有七组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 13 | $k = 1$。 | | 2 | 8 | $n \leq 20$，$k \leq 10$。 | | 3 | 11 | $n \leq 3000$，$k \leq 2$。 | | 4 | 15 | $k \leq 2$。 | | 5 | 26 | $n \leq 3000$，$k \leq 15$。 | | 6 | 17 | $k \leq 15$。 | | 7 | 10 | 无额外限制。 |