← 返回题目列表

AtCoder · icpc2013summer_day3_i

L. 京都之旅

中文机器翻译题面 查看原题
这个问题的遗漏已经被修改,请提交答案。非常抱歉给您带来不便。

京都这座城市以古老的寺庙和神社闻名,是著名的旅游胜地。

池田君和几位朋友一起来到京都观光,但由于大家各行其道,结果都迷路了。

因此,Ikuta君决定考虑,为了尽快与全员会合,应将集合地点设在哪里比较好。

京都的道路在东西方向和南北方向上以10的间隔无数延伸,可以视为无限延伸的正方形格栅。

道路被视为直线,道路宽度视为无。 另外,以城市中心为基准向东移动距离x、向北移动距离y的位置表示为(x,y)的坐标。

在城市中心(0,0)东西方向的道路和南北方向的道路相交。

下图表示了京都的道路以及一些点的坐标。

N人的游客坐标(Xi,Yi)以整数给出,N请回答人们在道路上移动以集合到一点所需时间的最小值。

假设游客可以以每单位时间距离1的速度连续地在道路上移动。

已知N每个游客的坐标彼此不同,且保证所有坐标都在道路上。

另外,也假设多个游客可以同时在同一点,或者游客之间可以错开移动。

输入

输入以以下格式给出。

N
X1 Y1
...
XN YN

第1行的N是游客的×。 接下来的N行中,第i行(1\leq i \leq N)表示第i个游客的位置(Xi, Yi)。 Xi,Yi均以整数给出。

约束

输入中的各变量满足以下否定。

  • 2 \leq N \leq 10000

  • -108 \leq Xi, Yi \leq 108

  • i \neq j 当 (Xi, Yi) \neq (Xj, Yj)

  • Xi 和 Yi 中至少有两个是10的倍数

输出

将问题的解输出在一行。 10-3允许绝对误差到

示例输入 1

3
5 10
-10 0
3 -10

样本输入 1 的输出

14
  • (0, 1)就可以了(这个输入例子与问题文中的图对应)

示例输入 2

2
0 0
0 1

样本输入 2 的输出

0.5
  • (0, 0.5)即可(注意也有可能集合在整数坐标以外的情况)

示例输入 3

4
100000000 100000000
100000000 -100000000
-100000000 100000000
-100000000 -100000000

样本输入 3 的输出

200000000