TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3624
  • 题目
  • P3624何老板快递
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB  SPJ
    问题描述

    近几年,快递业务发展迅速,何老板也打算涉足快递行业。何老板快递与普通快递不同,他打算用无人机收发快递,从快递业务点到用户之间是直线飞行,这样就不再受道路的限制可以大大提高快递的效率。


    在一条笔直公路的两侧分布有n个小区,何老板打算在这条公路边建一个无人机快递业务点,对这n个小区提供快递服务。
    无人机是有航程限制的,所以何老板想知道在哪个位置建立业务点可以使得业务点到与该点距离最远的那一个小区的航程尽可能小,请你找出这个位置。

    为简化问题,我们可以把笔直公路看作x坐标轴,把n个小区看作坐标平面上的n个点,现在告诉你每个点的坐标,要求在x轴上找一个点,使得这个点到n个点的距离中,最大的那一个尽可能小。

    输入格式

    第一行,一个整数n,表示有n个小区。
    接下来n行,每行两个实数x和y,表示一个小区的坐标,所有的小区位置都不相同

    输出格式

    一行,一个实数,表示满足要求的快递业务点的x坐标,保留3个小数位

    样例输入

    输入样例1
    2
    1.5 1.5
    3 0

    输入样例2
    5
    4 7
    -4 0
    7 -6
    -2 4
    8 -5

    输入样例3
    8
    -6.5 -14.5
    -1.01 11.02
    -5 0
    13.8 14
    -9 -14.125
    8 15
    -6.007 4.015
    5.03 11.7 

    样例输出

    输出样例1
    1.500

    输出样例2
    3.136

    输出样例3
    2.323

    提示

    为避免精度差,在进行距离计算时,直接比较(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2),不用sqrt开方。
    开方反而会有精度差!

    对于30%的数据1 ≤ n ≤ 1000

    对于100%的数据1 ≤ n ≤ 50000  , -200000 ≤ x, y ≤ 200000

    与标准答案误差在0.001以内的都会被认为是正确答案。


    来源  改编自Southwestern Europe Regional Contest 2009