两个吃奶一个添下面视频_人妻第一页香蕉网_欧美xxxx少妇_妺妺窝人体色www婷婷

原題來自：Waterloo University 2002

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

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

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

例如，對于下面三座村莊：

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

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

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

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

3 2
10 10
10 0
30 0

10.00

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

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