在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点用整数坐标(x,y)表示。士兵们可以沿网格边往上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一行。
编程计算使所有士兵排成一行需要的最少移动步数。
题目引自POJ
输入格式:
第1行是士兵数n，1≤n≤10000。接下来n行是士兵的初始位置，每行有2个整数x和y，-10000≤x，y≤10000。
输出格式:
一个数据，即士兵排成一行需要的最少移动步数。
输入样例:
5
1 2
2 2
1 3
3 -2
3 3
输出样例:
8
士兵排对分为x方向和y方向 所以我们可以把x和y分开来思考 类似与输油管道问题
对于Y方向
设n个士兵的Y轴坐标分别为：Y1，Y2 …… …… Yn， 他们最后站在同一行上，设目标坐标为Y0，
则n个士兵最终在Y轴的需要移动的总的步数值为S1：
S1=|Y1-Y0|+|Y2-Y0|+ …… …… +|Yn-Y0|
结论：Y0取所有Yi的中间值时可以使得S1达到最小（这个结论可以证明）
对所有的Y轴坐标进行排序（O（nlogn））或者进行线性时间选择（O（n））然后取“中间”点的Y轴坐标值作为最佳位置Y0的值
对于X方向
（1）首先需要对所有士兵的X轴坐标值进行排序（为了方便就近移动）
（2）然后，按从左至右的顺序依次求出每个士兵所对应的“最终位置”（最优），所移动的步数总和就是X轴方向上需要移动的步数
设排序后n个士兵在X轴坐标为： X1’，X2’ …… …… Xn’
他们最终位置”的X轴坐标值为：X0，X0+1，X0+2 …… …… X0+(n-1)
则n个士兵最终X轴的需要移动的总的步数值为S2：
S2=|X1’-X0| + |X2’-(X0+1)|+… +|Xn’-(X0+n-1)|
经过变换
S2=|X1’-X0|+ |(X2’-1)-X0|+ …+|(Xn’-(n-1))-X0|
注意到公式的形式与Y轴方向上的考虑一样，同样是n个已知数分别减去一个待定数后取绝对值，然后求和
结论：求出x1’, x2’-1,… Xn’-(n-1) 的中位数，即求得X0值，最后算出最优解。
采用二分排序（快排）
#include<stdio.h>
#include<stdlib.h>
typedef struct loc{
int *x;
int *y;
}Coordinate;
void sort(int a[],int left,int right){
int i,j,temp,t;
if(left>right){
return ;
}
temp = a[left];
i = left;
j = right;
while(i!=j){
while(a[j]>=temp&&i<j)
j--;
while(a[i]<=temp&&i<j)
i++;
if(i<j){
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
a[left] = a[i];
a[i] = temp;
sort(a,left,i-1);
sort(a,i+1,right);
}
int main(){
int i,n,x;
scanf("%d",&n);
Coordinate p;
p.x = (int *)malloc(sizeof(int)*n);
p.y = (int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++){
scanf("%d %d",&(p.x[i]),&(p.y[i]));
}
sort(p.y,0,n-1);
int sum=0;
x = p.y[n/2];
for(i=0;i<n;i++){
sum+=abs(p.y[i]-x);
}
sort(p.x,0,n-1);
for(i=0;i<n;i++){
p.x[i] = p.x[i]-i;
}
sort(p.x,0,n-1);
x = p.x[n/2];
for(i=0;i<n;i++){
sum+=abs(p.x[i]-x);
}
printf("%d",sum);
}