3618 - [GESP八级202606] 线网建设

题目描述

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

样例

输入

4 2
1 0
-1 -1
0 0
1 1

输出

3.41

输入

4 1
1 0
-1 -1
0 0
1 1

输出

Impossible
说明

提示

数据范围

  • 对于 40\% 的测试点,保证 1 \le n \le 100
  • 对于 100\% 的测试点,保证 1 \le n \le 5001 \le l \le 100-100 \le x_i, y_i \le 100
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 5 枚
难度 提高


上一题 下一题