A128415.[GESP202606 八级] 线网建设

普及-

GESP

通过率:0%

时间限制:1.00s

内存限制:512MB

题目描述

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

ii 座基站与第 jj 座基站之间的距离定义为 (xixj)2+(yiyj)2\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}

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

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

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

输入格式

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

接下来 nn 行,每行两个整数 xi,yix_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

输入解题思路,AI测评打分。不知道怎么写?

首页