5702: 城市的中心
[Creator : ]
Description
有一些大城市的道路,都是相互平行或垂直的,所以在城市间行走,不能用两点间的欧几里得距离计算长度,而是应该使用曼哈顿距离计算长度。两点间的曼哈顿距离定义如下:设两点的坐标分别为 $(x,\ y)$ 与 $(x^′,\ y^′)$,它们之间的曼哈顿距离定义为
$∣x−x^′∣+∣y−y^′∣$
给定二维平面上的 $n$ 个点的坐标,请在二维平面上找到一个中心点,使得给定的这些点到这个中心点的曼哈顿距离之和最小,输出这个最小值。
$∣x−x^′∣+∣y−y^′∣$
给定二维平面上的 $n$ 个点的坐标,请在二维平面上找到一个中心点,使得给定的这些点到这个中心点的曼哈顿距离之和最小,输出这个最小值。
Input
第一行:单个正整数 $n$。
第二行到第 $n+1$ 行:第 $i+1$ 行有两个整数 $x_i$ 和 $y_i$,表示一个点的坐标。
第二行到第 $n+1$ 行:第 $i+1$ 行有两个整数 $x_i$ 和 $y_i$,表示一个点的坐标。
Output
单个自然数:表示最优中心到各个点的曼哈顿距离之和。
Constraints
$−5000≤x_i,\ y_i≤5000$;
对于 $30\%$ 的数据,$1≤n≤20$;
对于 $60\%$ 的数据,$1≤n≤2000$;
对于 $100\%$ 的数据,$1≤n≤100000$;
对于 $30\%$ 的数据,$1≤n≤20$;
对于 $60\%$ 的数据,$1≤n≤2000$;
对于 $100\%$ 的数据,$1≤n≤100000$;
Sample 1 Input
4
1 0
0 1
-1 0
0 -1
Sample 1 Output
4
最优中心应该设置在 $(0,\ 0)$ 处。