2538 - 冷饮店选址

题目描述

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

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

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

输入

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

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

输出

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

样例

输入

5
1 2
2 2
1 3
3 -2
3 3

输出

10

输入

7
12 0
0 19
0 15
0 0
1 10
0 -1
-1 -1

输出

60

输入

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

输出

405
说明

说明

|x| 表示求 x 的绝对值,如果 x 是非负整数,则 x 的绝对值是自己,如果 x 是否负整数,则 x 的绝对值为相反数。比如,|2|=2|-2|=2

样例 1 解释

将Bob的冷饮店建在坐标 2,2 处,可以使得该点到所有住户距离的和最小。

数据范围

对于 50\% 的数据,满足 1 \le n \le 100,房子的坐标 x,y 满足 -200 ≤ x,y ≤ 200

对于 100\% 的数据,满足 1 \le n \le 10000,房子的坐标 x,y 满足 -10000 ≤ x,y ≤ 10000

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 523
通过人数 331
金币数量 2 枚
难度 基础


上一题 下一题