题面
题解
对于两个点((x_i,y_i))和(x_j,y_j)，我们定义它们之间的曼哈顿距离为
[|x_i-x_j|+|y_i-y_j|
]
定义它们的切比雪夫距离为
[max(|x_i-x_j|,|y_i-y_j|)
]
有如下转换：
将原坐标为((x,y))的点转化为((x+y,x-y))之后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离
将原坐标为((x,y))的点转化为(({x+yover 2},{x-yover 2}))之后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离
这里只证后一个，因为前一个就是它反过来
证明：
首先我们有一个结论
[maxleft({|a+b|,|a-b|}
ight)=|a|+|b|
]
分类讨论就能证明了
那么两个点重构之后的坐标为(({x_i+y_iover 2},{x_i-y_iover 2}),({x_j+y_jover 2},{x_j-y_jover 2}))，设为((x_i',y_i'),(x_j',y_j'))，那么现在它们之间的距离为
[egin{aligned}
Ans
&=max(|x_i-x_j|,|y_i-y_j|)\
&=max(|(x_i'+y_i')-(x_j'+y_j')|,|(x_i'-y_i')-(x_j'-y_j')|)\
&=max(|(x_i'-x_j')+(y_i'-y_j')|,|(x_i'-x_j')-(y_i'-y_j')|)\
&=|x_i'-x_j'|+|y_i'-y_j'|
end{aligned}
]
然后这题把切比雪夫距离转化为曼哈顿距离就可以了
关于如何计算曼哈顿距离的和呢？我们可以按(x)坐标和(y)坐标排个序，前缀和搞一下就可以了，具体可以看代码
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
const int N=1e5+5;
ll sum[N],res,tmp;int x[N],y[N],n;
struct node{
int v,id;
inline node(){}
inline node(R int vv,R int ii):v(vv),id(ii){}
inline bool operator <(const node &b)const{return v<b.v;}
}p[N];
int main(){
// freopen("testdata.in","r",stdin);
n=read(),res=1e18;
for(R int i=1,dx,dy;i<=n;++i)dx=read(),dy=read(),x[i]=dx+dy,y[i]=dx-dy;
fp(i,1,n)p[i]=node(x[i],i);
sort(p+1,p+1+n);
tmp=0;
fp(i,1,n)sum[p[i].id]+=1ll*(i-1)*p[i].v-tmp,tmp+=p[i].v;
tmp=0;
fd(i,n,1)sum[p[i].id]+=tmp-1ll*(n-i)*p[i].v,tmp+=p[i].v;
fp(i,1,n)p[i]=node(y[i],i);
sort(p+1,p+1+n);
tmp=0;
fp(i,1,n)sum[p[i].id]+=1ll*(i-1)*p[i].v-tmp,tmp+=p[i].v;
tmp=0;
fd(i,n,1)sum[p[i].id]+=tmp-1ll*(n-i)*p[i].v,tmp+=p[i].v;
fp(i,1,n)cmin(res,sum[i]);
printf("%lld
",res>>1);
return 0;
}