原題來(lái)自：Waterloo University 2002

北極的某區(qū)域共有 n 座村莊，每座村莊的坐標(biāo)用一對(duì)整數(shù) (x,y) 表示。為了加強(qiáng)聯(lián)系，決定在村莊之間建立通訊網(wǎng)絡(luò)。通訊工具可以是無(wú)線電收發(fā)機(jī)，也可以是衛(wèi)星設(shè)備。所有的村莊都可以擁有一部無(wú)線電收發(fā)機(jī)， 且所有的無(wú)線電收發(fā)機(jī)型號(hào)相同。但衛(wèi)星設(shè)備數(shù)量有限，只能給一部分村莊配備衛(wèi)星設(shè)備。

不同型號(hào)的無(wú)線電收發(fā)機(jī)有一個(gè)不同的參數(shù) d，兩座村莊之間的距離如果不超過(guò) d 就可以用該型號(hào)的無(wú)線電收發(fā)機(jī)直接通訊，d 值越大的型號(hào)價(jià)格越貴。擁有衛(wèi)星設(shè)備的兩座村莊無(wú)論相距多遠(yuǎn)都可以直接通訊。

現(xiàn)在有 k 臺(tái)衛(wèi)星設(shè)備，請(qǐng)你編一個(gè)程序，計(jì)算出應(yīng)該如何分配這 k 臺(tái)衛(wèi)星設(shè)備，才能使所擁有的無(wú)線電收發(fā)機(jī)的 d 值最小，并保證每?jī)勺迩f之間都可以直接或間接地通訊。

例如，對(duì)于下面三座村莊：

其中 |AB|=10,|BC|=20,|AC|=10–√5≈22.36

如果沒(méi)有任何衛(wèi)星設(shè)備或只有 1 臺(tái)衛(wèi)星設(shè)備 (k=0或 k=1)，則滿足條件的最小的 d=20，因?yàn)?nbsp;A和 B，B和 C 可以用無(wú)線電直接通訊；而 A 和 C可以用 B 中轉(zhuǎn)實(shí)現(xiàn)間接通訊 (即消息從 A 傳到 B，再?gòu)?nbsp;B 傳到 C)；

如果有 2 臺(tái)衛(wèi)星設(shè)備 (k=2），則可以把這兩臺(tái)設(shè)備分別分配給 B 和 C ，這樣最小的 d 可取 10，因?yàn)?nbsp;A 和 B 之間可以用無(wú)線電直接通訊；B 和 C 之間可以用衛(wèi)星直接通訊；A 和 C 可以用 B 中轉(zhuǎn)實(shí)現(xiàn)間接通訊。

如果有 3 臺(tái)衛(wèi)星設(shè)備，則 A,B,C 兩兩之間都可以直接用衛(wèi)星通訊，最小的 d 可取 0。

3 2
10 10
10 0
30 0

10.00

數(shù)據(jù)范圍:

對(duì)于全部數(shù)據(jù)，1≤n≤500,0≤x,y≤10⁴,0≤k≤100。