TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1756
  • 题目
  • P1756【Week8】极地网络
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    国防部想要通过无线网络与北极地区的一些军事哨所建立通讯连接。有两种不同的通讯技术将要被用来建立这个网络系统:无线电和卫星电话。每个哨所都将配置无线电收发器。只有部分哨所将配置卫星电话。
    任意两个配置了卫星电话的哨所可以通过卫星来通信,卫星通信不受地域和距离的限制。但是任意两个哨所想要通过无线电来通信的话,就有距离限制了,两者的距离不能超过D公里,这个距离D由无线电收发器的功率决定。无线电设备的功率越大,通信距离越远,但是价格也越高。处于价格和保养的考虑,国防部决定所有的哨所都使用相同的无线电收发器,也就是说每个哨所的无线电收发器的最大通信距离D都是相同的。
    你的工作就是决定无线电设备的传输距离D最小应该是多少,才能保证任意两个哨所间都有直接或间接的通信线路可以通信。

    输入格式

    第一行两个整数S(1 <= S <= 100)和P(S < P <= 500),S表示可供使用的卫星电话的数量,P表示哨所的数量。
    接下来P行,每行两个整数X和Y,表示一个哨所的位置坐标,单位是公里。(0<=X,Y<=10000)

    输出格式

    一个包含两个小数位的实数,表示无线电设备的最小通信距离。

    样例输入

    2 4
    0 100
    0 300
    0 600
    150 750

    样例输出

    212.13

    提示

    将2个卫星电话分配给第2和第3哨所
    第2、3哨所直接用卫星电话通信
    第1、3哨所的距离为200
    第3、4哨所的距离为212.13


    来源  Waterloo local 2002.09.28 root翻译