A7439. [GESP202606 八级] 线网建设
编程题
普及-
知识点
题目描述
A 市有 $n$ 座基站需要通过线网互相连接。第 $i$ 座基站位于二维平面上坐标 $(x_i, y_i)$ 处。
第 $i$ 座基站与第 $j$ 座基站之间的距离定义为 $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$。
如果两座基站之间的距离不超过给定的整数 $l$，那么可以修建连接这两座基站的线路，线路长度为基站间的距离。
如果从一座基站出发，经过一系列线网中的线路可以到达另一座基站，则称这两座基站是互相连接的。
请问使得 $n$ 座基站两两之间都互相连接，需要修建的线路总长度最小是多少？如果不能修建满足条件的线网，则输出
第 $i$ 座基站与第 $j$ 座基站之间的距离定义为 $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$。
如果两座基站之间的距离不超过给定的整数 $l$，那么可以修建连接这两座基站的线路，线路长度为基站间的距离。
如果从一座基站出发，经过一系列线网中的线路可以到达另一座基站，则称这两座基站是互相连接的。
请问使得 $n$ 座基站两两之间都互相连接，需要修建的线路总长度最小是多少？如果不能修建满足条件的线网，则输出
Impossible。输入格式
第一行，两个正整数 $n, l$，分别表示基站数量与线路长度上限。
接下来 $n$ 行，每行两个整数 $x_i, y_i$，表示基站的坐标。
接下来 $n$ 行，每行两个整数 $x_i, y_i$，表示基站的坐标。
输出格式
输出一行。如果能修建满足条件的线网，则输出需要修建的最小线路总长度，保留两位小数。否则输出
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