题目描述

Johnny和他的朋友们决定在万圣节夜晚收集村庄里的糖果。村庄中有$n$栋房屋（$1 \leq n \leq 50,000$），每栋房屋的坐标为平面直角坐标系中的$(x,y)$点。他们约定在河流（直线$y=0$）上选择一个集合点，使得所有人从各自分配的房屋出发并返回集合点的最晚到达时间最小化。

输入格式

• 每组测试数据：
  • 第一行：房屋数量$n$
  • 随后$n$行：每行两个浮点数$x,y$表示房屋坐标（$-200,000 \leq x,y \leq 200,000$）
  • 以空行分隔测试数据
  • 输入以$n=0$结束

输出格式

每组数据输出一行，包含：

1. 集合点的$x$坐标
2. 最晚到达时间（秒）

要求输出结果与标准答案的绝对或相对误差不超过$10^{-5}$。

样例输入

2
1.5 1.5
3 0

1
0 0

4
1 4
4 4
-3 3
2 4

样例输出

1.500000000 1.500000000
0.000000000 0.000000000
1.000000000 5.000000000

数据范围

• 房屋坐标：$-200,000 \leq x,y \leq 200,000$
• 房屋数量：$1 \leq n \leq 50,000$

题目来源

2009年西南欧地区竞赛