题意：
求\(n\)个点的切比雪夫距离和值的最小值
切比雪夫距离：对于\(x_1,y_1,x_2,y_2\)定义两个点的切比雪夫距离为\(max(|x_1-x_2|,|y_1-y_2|)\)
范围&性质：\(1\le n\le 10^5,-10^9\le x,y \le 10^9\)
分析：
首先我们先来了解一个小结论：
枚举到\((0,0)\)点曼哈顿距离为1的点：
\((1,0),(0,1),(-1,0),(0,-1),(0.5,0.5),(0.5,-0.5),(-0.5,-0.5),(-0.5,0.5)\)
枚举到\((0,0)\)点切比雪夫距离为1的点：
\((0,1),(1,1),(-1,1),(-1,-1),(0,-1),(1,-1),(1,0),(-1,0)\)
将上述的点画在坐标系里可以得到两个正方形，且第二个是第一个向左旋转\(45^\circ\)后扩展2倍得到
由此我们可以推得
将一个点\((x,y)\)的坐标变为\((x+y,x−y)\)后,原坐标系中的曼哈顿距离 \(=\)新坐标系中的切比雪夫距离
将一个点\((x,y)\)的坐标变为\((\frac {x+y}2,\frac {x-y}2)\) 后,原坐标系中的切比雪夫距离 \(=\) 新坐标系中的曼哈顿距离
由以上结论我们可以将给定点的切比雪夫距离转化为曼哈顿距离，对于每一个点他的坐标变化为了\((gx,gy)\)
由于曼哈顿距离有一个优越的性质：可以快速求多个点到一个点的距离和值，所以我们对于新的点进行排序
记枚举的松鼠为\(k\),那么：
\[ans= \sum_{i=1}^n dis(i,k)=\sum_{i=1}^n[ \;|gx_i-gx_k| \;+\; |gy_i-gy_k|\; ]
\]
化简得到
\[ans=|gx_1-gx_k|+|gx_2-gx_k| \dots + +|gx_n-gx_k|+|gy_1-gy_k|+|gy_2-gy_k|\dots +|gy_n-gy_k|
\]
只要维护一下前缀和就可以将复杂度降到单次\(\omicron(1)\)
代码：
#include<bits/stdc++.h>
using namespace std;
namespace zzc
{
const int maxn = 1e5+5;
long long x[maxn],y[maxn],nx[maxn],ny[maxn];
long long sumx[maxn],sumy[maxn];
long long ans,n;
long long calc(long long i)
{
long long tmpx=lower_bound(nx+1,nx+n+1,x[i])-nx;
long long tmpy=lower_bound(ny+1,ny+n+1,y[i])-ny;
return ( (tmpx*x[i]-sumx[tmpx]+sumx[n]-sumx[tmpx]-(n-tmpx)*x[i]) ) + ( tmpy*y[i]-sumy[tmpy]+sumy[n]-sumy[tmpy]-(n-tmpy)*y[i] );
}
void work()
{
scanf("%lld",&n);
for(long long i=1,a,b;i<=n;i++)
{
scanf("%lld%lld",&a,&b);
x[i]=nx[i]=a+b;
y[i]=ny[i]=a-b;
}
sort(nx+1,nx+n+1);
sort(ny+1,ny+n+1);
for(long long i=1;i<=n;i++)
{
sumx[i]=sumx[i-1]+nx[i];
sumy[i]=sumy[i-1]+ny[i];
}
ans=0x7ffffffffffff;
for(long long i=1;i<=n;i++)
{
ans=min(ans,calc(i));
}
printf("%lld",ans>>1);
}
}
int main()
{
zzc::work();
return 0;
}