← 返回题目
题库练习 线网建设
← 上一题 下一题 →

A72041 | 线网建设

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

A 市有 n 座基站需要通过线网互相连接。第 i 座基站位于二维平面上坐标 (x_i,y_i) 处。

第 i 座基站与第 j 座基站之间的距离定义为 \sqrt{(x_i-x_j)^2+(y_i-y_j)^2}。

如果两座基站之间的距离不超过给定的整数 l，那么可以修建连接这两座基站的线路，线路长度为基站间的距离。

如果从一座基站出发，经过一系列线网中的线路可以到达另一座基站，则称这两座基站是互相连接的。

请问使得 n 座基站两两之间都互相连接，需要修建的线路总长度最小是多少？如果不能修建满足条件的线网，则输出 Impossible。

输入格式

第一行，两个正整数 n,l，分别表示基站数量与线路长度上限。

接下来 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
C++ 编辑器
输入
输出