[Beijing wc2012]灵魂宝石

时间限制:5s      空间限制:128MB

题目描述

【问题描述】
“作为你们本体的灵魂,为了能够更好的运用魔法,被赋予了既小巧又安全
的外形,„„”
 
  我们知道,魔法少女的生命被存放于一个称为灵魂宝石(Soul Gem)的装置
内。而有时,当灵魂宝石与躯体的距离较远时,魔法少女就无法控制自己的躯体
了。
  
  在传说中,魔法少女 Abel仅通过推理就得到了这个现象的一般法则,被称为
Abel定理:  
  存在宇宙常量 R(是一个非负实数,或正无穷) ,被称为灵魂宝石常量,量
纲为空间度量(即:长度) 。如果某个魔法少女的灵魂宝石与她的躯体的距离严
格超过 R,则她一定无法控制自己的躯体;如果这个距离严格小于 R,则她一定
可以控制自己的躯体。 (这里的距离指平面的 Euclid距离。)
  注意:该定理不能预言距离刚好为 R 的情形。可能存在魔法少女 A 和 B,她
们离自己的灵魂宝石的距离都恰好为 R,但是 A可以控制自己的躯体,而 B 不可
以。
   现在这个世界上再也没有魔法少女了,但是我们却对这个宇宙常量感兴趣。
我们只能通过之前的世界遗留下来的数据来确定这个常量的范围了。
  每一组数据包含以下信息:
    ·一共有N 个魔法少女及她们的灵魂宝石,分别编号为 1~N。
    ·这 N个魔法少女所在的位置是(Xi, Yi)。
    ·这 N个灵魂宝石所在的位置是(xi, yi)。
    ·此时恰好有 K个魔法少女能够控制自己的躯体。
  需要注意的是:
1. 我们认为这个世界是二维的 Euclid 空间。
    2. 魔法少女与灵魂宝石之间的对应关系是未知的。
    3. 我们不知道是具体是哪 K个魔法少女能够控制自己的躯体。
    
  根据以上信息,你需要确定灵魂宝石常量 R可能的最小值 Rmin 和最大值
Rmax。


输入格式

第一行包两个整数:N、K。
接下来 N行,每行包含两个整数:Xi , Yi ,由空格隔开。
再接下来N 行,每行包含两个整数:xi , yi ,由空格隔开。 
 


输出格式

输出两个量:Rmin、Rmax,中间用空格隔开。
Rmin 一定是一个非负实数,四舍五入到小数点后两位。
Rmax 可能是非负实数,或者是正无穷:
  如果是非负实数,四舍五入到小数点后两位;
  如果是正无穷,输出“+INF”(不包含引号)。


样例输入

2 1 
1 0 
4 0 
0 0 
4 4 

样例输出

1.00 5.00 

 

提示

对于100%的数据:
1 ≤  N  ≤  50,
0 ≤  K  ≤  N,
-1000 ≤  xi, yi , Xi , Yi  ≤  1000。 
 


题目来源

没有写明来源

Menuappsclose