本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1037. 跟着CoolGuangr去春游


Description

【问题描述】

小朋友春游问题(难度系数3):

问题描述:

学校老师要组织小朋友春游,假定所有小朋友都住在一个按东西和南北方向正规划分成的街区里,n 个小朋友散乱地分布在不同的地点中。x 坐标表示东西向,y 坐标表示南北向。各小朋友的位置可由坐标(x,y)表示。

此处,任意 2 点(x 1 ,y 1 )和(x 2 ,y 2 )之间的距离用数值| x 1 - x 2 |+| y 1 - y 2 |度量。

    学校老师希望找到一个最佳的集合地点,使 n 个小朋友到集合地点的距离总和最小。


Input

【输入形式】

数据输入:

输入数据的第 1 行是小朋友人数n,1≤n≤10000。接下来 n 行是小朋友的位置,每行 2 个整数 x 和 y,以空格分隔,-10000≤x,y≤10000。(假定没有2人以上居住在同一地点)。

Output

结果输出:

输出距离总和的最小值。

Samples

Input Copy
3
-4 -3
-4 5
5 2
Output
17

Source

2019徐州工程学院新生赛
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 2 / 2
Tags:
My history solutions

You didn't submit any solution!
Submit your solution

Login Register