P10164: 邮局选址问 题
传统题
1.000s
时间限制
128MB
内存限制
5 提交
3 解决
【题目描述】
在一个按照东西和南北方向划分成规整街区的城市里，
n 个居民点散乱地分布在不同的
街区中。用
x 坐标表示东西向，用
y 坐标表示南北向。各居民点的位置可以由坐标
(x,y)表示。
街区中任意
2 点
(x1,y1)和
(x2,y2)之间的距离可以用数值
|x1-x2|+|y1-y2|度量。
居民们希望在城市中选择建立邮局的最佳位置，使
n 个居民点到邮局的距离总和最小。
«编程任务：
给定 n 个居民点的位置
,编程计算 n
个居民点到邮局的距离总和的最小值。
【输入】
第 1 行是居民点数 n，1£n£10000。接下来 n 行
是居民点的位置，每行 2 个整数 x 和 y，-10000£x，y£10000。
【输出】
第 1 行中的数是 n 个居
民点到邮局的距离总和的最小值。
【样例输入】复制
5
1 2
2 2
1 3
3 -2
3 3