← 返回题目
题库练习 冷饮店选址
← 上一题 下一题 →

A71432 | 冷饮店选址

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

炎热的夏天到了，Bob 准备在小镇上开一家冷饮店，开店选址是一门大学问，为了让自己的店火爆起来，Bob 要精心选择自己的开店地址。

小镇的道路规划是横平竖直的。如果将小镇想象成坐标轴，小镇中任意两个房子 (x_1,y_1) 和 (x_2,y_2) 之间的距离，可以直接用曼哈顿距离来计算，也就是 = |x_1-x_2| + |y_1-y_2| 。

现在已经统计到了小镇上所有住户房子的坐标值，请你帮 Bob 选一下冷饮店的地址，使得该点到所有住户房子的距离和最小。（请注意：允许选到的开冷饮店的位置，是某住户房子的位置，也允许选到开冷饮电的位置，不是某住户房子的位置）

输入格式

第1行输入一个整数 n ，代表了小镇有n个住户。

接下来 n 行，每行有 2 个整数 x 和 y，表示小镇中某个住户的房子的坐标值。

输出格式

请输出 Bob 的冷饮店，到所有住户的房子距离和的最小值。

输入输出样例

输入 #1
5
1 2
2 2
1 3
3 -2
3 3
输出 #1
10
输入 #2
7
12 0
0 19
0 15
0 0
1 10
0 -1
-1 -1
输出 #2
60
输入 #3
15
-25 -31
-9 -9
7 30
7 -13
0 -4
14 10
10 -5
1 -34
-3 -36
-1 -6
2 -4
2 10
12 14
9 14
13 90
输出 #3
405
C++ 编辑器
输入
输出