这个问题的遗漏已经被修改,请提交答案。非常抱歉给您带来不便。
京都这座城市以古老的寺庙和神社闻名,是著名的旅游胜地。
池田君和几位朋友一起来到京都观光,但由于大家各行其道,结果都迷路了。
因此,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