3088: 城市的中心

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:12 解决:11

题目描述

大城市的道路是相互平行或垂直的,如果在城市的道路上行走,不能用点与点之间的直线距离计算长度,而是应该定义两个点(设坐标分别为 (�,�)(x,y) 与 (�′,�′)(x,y))的城市距离为

∣�−�′∣+∣�−�′∣xx+yy

给定 n 个点的坐标,请在二维平面中找到一个中心点,使得给定的这些点到这个中心点的城市距离之和最小,输出这个最小值。

输入

第一行:单个正整数 n
第二行到第 �+1n+1 行:第 �+1i+1 行有两个整数 ��xi 和 ��yi,表示一个点的坐标。

  • 5000xi,yi5000
  • 对于 30%30% 的数据,1≤�≤201n20
  • 对于 60%60% 的数据,1≤�≤20001n2000
  • 对于 100%100% 的数据,1≤�≤1000001n100000


输出

单个整数:表示各点到中心的距离之和的最小值。

样例输入 复制

4
1 0
0 1
-1 0
0 -1

样例输出 复制

4

提示

最优中心应该设置在(0,0)处