TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1756
  • Problem
  • P1756极地网络
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input 1

    2 4
    0 100
    0 300
    0 600
    150 750

    Sample Output 1

    212.13

    Sample Input 2

    1 2
    0 0
    100 100

    Sample Output 2

    141.42

    Hint

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


    Source  Waterloo local 2002.09.28 root翻译