Responsive image

问题 2385 --北极网络

2385: 北极网络

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

国防部(DND)希望通过无线网络连接几个北部前哨站。
在建立网络时将使用两种不同的通信技术:每个前哨站都有一个无线电收发器,一些前哨站还有一个通信卫星。
任意两个拥有通信卫星的前哨站不论它们的位置如何,都可以通过卫星进行通信。
而如果利用无线电进行通信,则需要两个前哨站的距离不能超过 D 方可进行通信。
而 D 的大小取决于收发器的功率,收发器的功率越大,D 也就越大,但是需要的成本也就越高。
出于采购和维护的考虑,所有的前哨站都采用相同的收发器,也就是说所有前哨站的无线电通信距离 D 都是相同的。
你需要确定在保证任意两个前哨站之间都能进行通信(直接或间接)的情况下,D 的最小值是多少。

输入描述

第一行包含整数 N,表示共有 N 组测试数据。
每组数据的第一行包含两个整数 S 和 P,其中 S 为卫星个数,P 为前哨站个数。
接下来 P 行每行包含两个整数 x 和 y,分别表示一个前哨站的横纵坐标。

输出描述

输出一个实数,表示 D 的最小值,结果保留两位小数。

样例输入

1
2 4
0 100
0 300
0 600
150 750

样例输出

212.13

提示

1≤S≤100,

S≤P≤500,

0≤x,y≤10000

来源

[提交][状态]
ACM算法攻关部