（POJ题目链接）

N soldiers of the land Gridland are randomly scattered around the country.
A position in Gridland is given by a pair (x,y) of integer coordinates. Soldiers can move - in one move, one soldier can go one unit up, down, left or right (hence, he can change either his x or his y coordinate by 1 or -1).

最开始看这题想到的就是枚举队伍的起点、计算每个士兵移动到对应位置的最短路。题目中并没有确定士兵排队的顺序，那么如何确定士兵移动到的「对应位置」呢？显然，按照X坐标排序，第1个士兵移动到队伍的第1个，第2个士兵移动到第2个，……，第N个士兵移动到第N个位置。唯一有问题的是如果有多个士兵X坐标相同怎么办呢？容易证明，按照任意顺序这些士兵走的路加和相等。

然而枚举起点需要O（（MaxX-MinX）²），计算士兵又需要O（N），时间复杂度接近10^12，肯定要超时。这时候我们会想到：能不能直接确定队伍的y坐标？如果我们不需要士兵移动到指定位置，只需要他们移动到队伍所在行（也就是在y轴方向移动），我们称此为「第一阶段」，怎样才能使士兵们「第一阶段」移动距离最小？假设队伍在第Y行，我们列出这样的式子：|Y1-Y|+|Y2-Y|+……+|Yn-Y|，这就是「第一阶段」需要移动距离总和。显然只要排序后Y取中位数就可以了。

但是这样的复杂度仍然是O（N²（MaxX-MinX）），最大达到210^8，还是要超时。这时候我们就会想到：能不能用类似的方法确定队伍起点的X坐标呢？仔细思考：如果队伍第一个横坐标为X，那么「第二阶段」需要移动距离总和就是：|X1-X|+|X2-(X+1)|+|X3-(X+2)|+……+|Xn-(X+n-1)|，变形得到：|X1-X|+|X2-1-X|+……+|Xn-n+1-X|，那么前面的Xi-i+1是可以构造的，排序取中位数又可以得到队伍第一个X坐标了！

还有一个问题是题目中规定：「Two or more soldiers must never occupy the same position at the same time. 」这个怎么解决？很简单，因为如果两个士兵X坐标不同，他们的路径一定不会相交；如果相同，有一个在前，更不会相交。

贴上代码：

#include
#include
#include
#include
using namespace std;
const int maxn=10005;
int n,midnum_x,midnum_y,tmp[maxn],ans=0;
struct WT{
    int x,y;
}a[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline bool cmp_by_y(WT aa,WT bb){
    return aa.y>1].y;
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++) tmp[i]=a[i].x-i+1;
    sort(tmp+1,tmp+1+n);
    midnum_x=tmp[(n+1)>>1];
    for (int i=1;i<=n;i++) ans+=getdst(a[i].x,a[i].y,midnum_x+i-1,midnum_y);
    printf("%d\n",ans);
    return 0;
}