若干年以后，良乡校区已经全部建设完毕。有许多的建筑和道路，它们纵横交错形成一个 n x m 的棋盘式网状布局。这个棋盘中的每一个横行和纵行均为一条道路，在某些道路交叉点上具有一栋建筑。每一栋建筑可以由一个二维坐标 (x,y) 表示，表示这一栋建筑处于第 x 横行、第 y 纵行的两条道路的交叉点上。
现在，良乡要在某一个道路交叉点上（可能已经有建筑）新建立一个供暖站。新的供暖站将修建供热管道到已有的每一栋建筑。为了方便维修，供暖管道只能直接修建在道路之下。为了最小化成本，良乡管理处想要让要修建的管道的总长度最小。
假定这个道路“棋盘”是单位均匀的（也就是每一个交叉点到相邻的四个交叉点之间的距离均为1）。现在良乡管理处想要知道，他们最少需要修建多长的管道。
输入描述
输入文件第一行为一个整数N [1,100 000] ，表示已有建筑的数量。
接下来的 N 行，每行包含两个以空格分隔的整数 x 和 y [-1 000 000 000, 1 000 000 000] ，分别表示每一栋建筑的坐标。
输出描述
输出一行一个整数表示需要新修建的管道的最短长度。
样例说明
对于第一组测试用例，供暖站应该建在坐标 (0, 0) 处，其到三个已有建筑的距离分别为 2, 2, 0，因此总距离为 4；
对于第二组测试用例，供暖站直接建在 (50, 50) 处即可。
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
| 测试用例 2 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
#include<stdio.h>
#include<math.h>
void merge(int b[],int n1,int c[],int n2,int a[],int n)
{ int i=0,j=0,k=0,u; while(i<n1&&j<n2) { if(b[i]<=c[j]) { a[k]=b[i]; i++; } else { a[k]=c[j]; j++; } k++; } if(i==n1) { for(u=k;u<n;u++,j++) a[u]=c[j]; } else { for(u=k;u<n;u++,i++) a[u]=b[i]; }
} void mergesort(int a[],int n)
{ int i; int n1,n2; n1=floor((float)n/2); n2=ceil((float)n/2); if(n>1) { int b[n1],c[n2]; for(i=0;i<n1;i++) b[i]=a[i]; for(i=0;i<n2;i++) c[i]=a[i+n1]; mergesort(b,n1); mergesort(c,n2); merge(b,n1,c,n2,a,n); }
}
int main(){ int n,i; scanf("%d",&n); int a[n],b[n],mid; long long x=0,y=0; for(i=0;i<n;i++) { scanf("%d%d",&a[i],&b[i]); } if(n==1) { printf("0\n"); return 0; } mergesort(a,n); mergesort(b,n); mid=n/2; for(i=0;i<n;i++) x+=abs(a[i]-a[mid]); for(i=0;i<n;i++) y+=abs(b[i]-b[mid]); printf("%ld\n",x+y);
}
