题目描述
草原上住着一群小松鼠,每个小松鼠都有一个家。时间长了,大家觉得应该聚一聚。但是草原非常大,松鼠们都很头疼应该在谁家聚会才最合理。

每个小松鼠的家可以用一个点x,y表示,两个点的距离定义为点(x,y)和它周围的8个点(x-1,y)(x+1,y),(x,y-1),(x,y+1).(x-1,y+1),(x-1,y-1),(x+1,y+1),(x+1,y-1)距离为1。

输入格式
第一行是一个整数N,表示有多少只松鼠。接下来N行,第i行是两个整数x和y,表示松鼠i的家的坐标

输出格式
一个整数,表示松鼠为了聚会走的路程和最小是多少。

输入输出样例
输入 #1复制
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
输出 #1复制
20
输入 #2复制
6
0 0
2 0
-5 -2
2 -2
-1 2
4 0
输出 #2复制
15
说明/提示
样例解释
在第一个样例中,松鼠在第二只松鼠家(-1,-2)聚会;在第二个样例中,松鼠在第一只松鼠家(0.0)聚会。

数据范围
30%的数据，0 ≤ N ≤ 1000

100%的数据，0 ≤ N ≤ 100000; −10^9 ≤ x, y ≤ 10^9

空间距离变换题目，实际没什么难度。

我们由切比雪夫距离和曼哈顿距离的变换可知：

将一个点(x,y)的坐标变为(x+y,x−y)后,原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离
将一个点(x,y)的坐标变为(x+y2,x−y2) 后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离

然后题目给出了切比雪夫距离，我们变为曼哈顿距离，然后曼哈顿距离，x和y的计算是可以分开的，然后我们计算前缀和，就可以分别算出贡献值了。

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,res=1e18,x[N],y[N],sx[N],sy[N];
struct node{int x,y;}t[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&x[i],&y[i]); t[i].x=x[i]+y[i]; t[i].y=x[i]-y[i];
        x[i]=t[i].x;    y[i]=t[i].y;
    }
    sort(x+1,x+1+n);    sort(y+1,y+1+n);
    for(int i=1;i<=n;i++)   sx[i]=x[i]+sx[i-1];
    for(int i=1;i<=n;i++)   sy[i]=y[i]+sy[i-1];
    for(int i=1;i<=n;i++){
        int l=lower_bound(x+1,x+1+n,t[i].x)-x;
        int r=lower_bound(y+1,y+1+n,t[i].y)-y;
        int s=l*t[i].x-sx[l]+(sx[n]-sx[l]-(n-l)*t[i].x);
        s+=r*t[i].y-sy[r]+(sy[n]-sy[r]-(n-r)*t[i].y);
        res=min(res,s);
    }
    cout<<(res>>1ll)<<endl;
    return 0;
}