格格兰郡的 N 名士兵随机散落在全郡各地。

格格兰郡中的位置由一对 (x,y) 整数坐标表示。

士兵可以进行移动，每次移动，一名士兵可以向上，向下，向左或向右移动一个单位（因此，他的 x 或 y 坐标也将加 1 或减 1）。

现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的 y 坐标相同并且 x 坐标相邻。

请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。

需注意，两个或多个士兵不能占据同一个位置。

输入格式
第一行输入整数 N，代表士兵的数量。

接下来的 N 行，每行输入两个整数 x 和 y，分别代表一个士兵所在位置的 x 坐标和 y 坐标，第 i 行即为第 i 个士兵的坐标 (x[i],y[i])。

输出格式
输出一个整数，代表所有士兵的总移动次数的最小值。

数据范围
1≤N≤10000,
−10000≤x[i],y[i]≤10000

输入样例：

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

输出样例：

8

参考答案

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fir(a,b,c) for (ll a=b;a<=c;a++)//宏定义for循环
const int N=10050;
ll x[N],y[N],n,x_mid,y_mid,ans=0;
int main() 
{
    ios::sync_with_stdio(false);
    cin>>n;
    fir(i,1,n)
        cin>>x[i]>>y[i];
    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    fir(i,1,n)
        x[i]-=i;
    sort(x+1,x+1+n);
    x_mid=x[(n+1)>>1];//x坐标的中位数
    y_mid=y[(n+1)>>1];//y坐标的中位数
    fir(i,1,n)
    {
        ans+=abs(x[i]-x_mid);
        ans+=abs(y[i]-y_mid);
    }
    cout<<ans;
    return 0;
}