这个距离就是切比雪夫距离，有一个神奇的东西是说将(x,y)变成(x+y,x-y)，然后就是曼哈顿距离，因此转化后对x坐标和y坐标分别统计排序和求和（求前缀和预处理+二分）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 struct ji{ 5 int x,y; 6 }a[N]; 7 int n,x,y,xx[N],yy[N]; 8 long long sx[N],sy[N],ans; 9 long long calc(int x,int y){ 10 int x0=lower_bound(xx+1,xx+n+1,x)-xx,y0=lower_bound(yy+1,yy+n+1,y)-yy; 11 return x*(2LL*x0-n)+y*(2LL*y0-n)-(2*sx[x0]-sx[n])-(2*sy[y0]-sy[n]); 12 } 13 int main(){ 14 scanf("%d",&n); 15 for(int i=1;i<=n;i++){ 16 scanf("%d%d",&x,&y); 17 a[i].x=x+y; 18 a[i].y=x-y; 19 xx[i]=x+y; 20 yy[i]=x-y; 21 } 22 sort(xx+1,xx+n+1); 23 for(int i=1;i<=n;i++)sx[i]=sx[i-1]+xx[i]; 24 sort(yy+1,yy+n+1); 25 for(int i=1;i<=n;i++)sy[i]=sy[i-1]+yy[i]; 26 ans=1e18; 27 for(int i=1;i<=n;i++)ans=min(ans,calc(a[i].x,a[i].y)); 28 printf("%lld",ans/2); 29 }