3088: 城市的中心
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：12
解决：11
题目描述
大城市的道路是相互平行或垂直的，如果在城市的道路上行走，不能用点与点之间的直线距离计算长度，而是应该定义两个点（设坐标分别为 (�,�)(x,y) 与 (�′,�′)(x′,y′)）的城市距离为
∣�−�′∣+∣�−�′∣∣x−x′∣+∣y−y′∣
给定 �n 个点的坐标，请在二维平面中找到一个中心点，使得给定的这些点到这个中心点的城市距离之和最小，输出这个最小值。
输入
第一行：单个正整数 �n。
第二行到第 �+1n+1 行：第 �+1i+1 行有两个整数 ��xi 和 ��yi，表示一个点的坐标。
第二行到第 �+1n+1 行：第 �+1i+1 行有两个整数 ��xi 和 ��yi，表示一个点的坐标。
- −5000≤xi,yi≤5000；
- 对于 30%30% 的数据，1≤�≤201≤n≤20；
- 对于 60%60% 的数据，1≤�≤20001≤n≤2000；
- 对于 100%100% 的数据，1≤�≤1000001≤n≤100000；
输出
单个整数：表示各点到中心的距离之和的最小值。
样例输入 复制
4
1 0
0 1
-1 0
0 -1样例输出 复制
4提示
最优中心应该设置在(0,0)处