A128415.[GESP202606 八级] 线网建设
普及-
GESP
通过率:0%
时间限制:1.00s
内存限制:512MB
题目描述
A 市有 n 座基站需要通过线网互相连接。第 i 座基站位于二维平面上坐标 (xi,yi) 处。
第 i 座基站与第 j 座基站之间的距离定义为 (xi−xj)2+(yi−yj)2。
如果两座基站之间的距离不超过给定的整数 l,那么可以修建连接这两座基站的线路,线路长度为基站间的距离。
如果从一座基站出发,经过一系列线网中的线路可以到达另一座基站,则称这两座基站是互相连接的。
请问使得 n 座基站两两之间都互相连接,需要修建的线路总长度最小是多少?如果不能修建满足条件的线网,则输出 Impossible。
输入格式
第一行,两个正整数 n,l,分别表示基站数量与线路长度上限。
接下来 n 行,每行两个整数 xi,yi,表示基站的坐标。
输出格式
输出一行。如果能修建满足条件的线网,则输出需要修建的最小线路总长度,保留两位小数。否则输出 Impossible。
输入输出样例
输入#1
4 2 1 0 -1 -1 0 0 1 1
输出#1
3.41
输入#2
4 1 1 0 -1 -1 0 0 1 1
输出#2
Impossible
输入解题思路,AI测评打分。不知道怎么写?