问题 21922 --北极网络

21922: 北极网络

时间限制: 2 Sec  内存限制: 128 MB
提交: 18  解决: 6
[提交][状态][讨论版][数据上传:][下载FPS2元][添加到购物车][下载测试数据2元][24kb]

题目描述

国家安全局希望把北极的数个前哨站用一个无线网络链接起来。为了建立网络,有两种不同的通讯技术可以使用,分别是无线电通信和卫星通信。每一个前哨站都拥有一个无线电收发器,部分前哨站额外拥有卫星通信器。

拥有卫星通信器的前哨站之间可以无视距离进行通信;而只有无线电收发器的前哨站则可以在不超过D的距离范围内进行通信,D的大小取决于收发器的功率大小。功率越高D值越大,不过消耗也就越多。出于设备购买与维护的考虑,所有前哨站的无线电收发器都是一致的,也就是所有收发器的D值都是一样的。

你的工作是确定无线电收发器所需的最小D值。

每一对前哨站之间都必须建立至少一条(直接或间接的)通信线路。


输入

数据的第一行是正整数N,代表数据的组数。
每一组测试数据的第一行为两个数S(1<=S<=100),代表卫星通信器的数量,还有P(S<P<=500),代表前哨站的数量。
其后P行,每行为一个前哨站的坐标(x,y)(x,y均为0到10000间的整数)。

输出

对于每一组测试数据,输出为一行,给出建立通信网络所需的最小的D值,精确到小数点后两位。

样例输入

1
2 4
0 100
0 300
0 600
150 750

样例输出

212.13

提示

来源

[提交][状态]