logo AlgoBeat OnlineJudge
登录 注册

#215393. [NHSPC 2025] 神聖的連線儀式

内存限制:512 MiB 时间限制:6000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

在遙遠的「座標王國」裡,大地上散落著 個祭壇。這些祭壇是王國與諸神溝通的媒介,每一個祭壇都有自己的名字與位置,而它們的位置總是整齊地記錄在平面座標上,永不重複,依序分別為

每逢百年一度的「能量甦醒節」,國王必須召集全國祭司,在大地上進行一場莊嚴神聖的連線儀式。傳說中,當某些祭壇之間以神聖的光束相連,能量就會在它們之間流動,進而喚醒沉睡的巨龍與大地之靈,守護整個王國。然而,儀式並不能隨意進行。祭司必須遵循古老的規則:

  1. 儀式中必須選出 條連線,其中 的值介於 之間。
  2. 每條連線都必須連接兩個不同的祭壇。
  3. 任何一個祭壇在整個儀式中至多只能參與一條連線,也就是說,所有連線的端點必須互不重複。
  4. 任兩條連線不可在平面上交叉或重疊,否則會彼此干擾。

能量的流動並非毫無代價。兩個祭壇之間的連線會消耗祭司們的法力,而法力的消耗量與它們的距離成正比,而第 個祭壇與第 個祭壇,即位置 與位置 ,之間的距離的定義是歐幾里得距離:

因此,如果選出的連線過長,對祭司們將會是沉重的負擔,如果法力不足,將會導致連線儀式無法完成。反之,如果能找到合適的祭壇,使得總連線距離最短,那麼儀式就能以最小的法力消耗完成,並且釋放出最大的能量。

作為王國的御用解題大師,你肩負重責大任。國王將祭壇的座標交給你,並要求你算出最小的總法力消耗。為了方便起見,我們採用連線的總長度來代表祭司們法力的總消耗量。你的答案將直接決定儀式能否順利完成,甚至影響王國的存亡。

输入格式

  • 為祭壇數量。
  • 為需要選出的連線數量。
  • 代表第 個祭壇的座標是

输出格式

  • 代表最小的總法力消耗。相對誤差或絕對誤差在 以下均視為正確。也就是說,若正確答案是 ,則你的答案只要滿足

    即會被視為正確。

样例

样例输入 1

3 1
0 0
0 3
9 9

样例输出 1

3.0000000000

样例输入 2

4 2
0 0
1 0
5 5
5 6

样例输出 2

2.0000000000

数据范围与提示

測資限制

  • 所有祭壇座標均不同。
  • 輸入的數皆為整數。

評分說明

本題共有七組子任務,條件限制如下所示。 每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

子任務 分數 額外輸入限制
1 13
2 8
3 11
4 15
5 26
6 17
7 10 無額外限制。