3418: 城市的中心
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：14
解决：6
题目描述
在一个大城市中，道路相互平行或垂直。给定若干个点的坐标，找到一个中心点，使得这些点到该中心点的城市距离之和最小，并输出这个最小值。城市距离定义为两点之间的曼哈顿距离，即 \(\lvert x - x' \rvert + \lvert y - y' \rvert\)。
输入
- 第一行：一个正整数 \(n\)，表示点的数量。
- 接下来的 \(n\) 行：每行包含两个整数 \(x_i\) 和 \(y_i\)，表示第 \(i\) 个点的坐标。
输出
- 一个整数：表示各点到中心的距离之和的最小值。
样例输入 复制
4
1 0
0 1
-1 0
0 -1样例输出 复制
4提示
- \(-5000 \leq x_i, y_i \leq 5000\)
- 对于 30% 的数据，\(1 \leq n \leq 20\)
- 对于 60% 的数据，\(1 \leq n \leq 2000\)
- 对于 100% 的数据，\(1 \leq n \leq 100000\)