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 | 無額外限制。 |