(\)
(Description)
给出(N)个整点的坐标，在坐标系中选择一个整点，使得这个整点到这(N)个点的切比雪夫距离之和最小。
- (Nin [1,10^5])，(x_i,y_iin [0,10^5])
(\)
(Solution)
- 首先对于一个点，切比雪夫距离并不好快速求出，考虑转化为曼哈顿距离，将每个点((x_i,y_i))变为((frac{x_i+y_i}{2},frac{x_i-y_i}{2}))，关于转化的部分可以参考：曼哈顿距离与切比雪夫距离的互化。
- 然后就是经典的运输问题，将两个坐标系的方向分开考虑，考虑一个坐标系上的问题，就是数轴上有一些点，选择一个点到所有点的距离和最小，这个的答案是中位数，可以通过微扰法证明。
- 于是将横纵坐标拆开排序，分别取中位数，因为选的点只要求是整点，并没有要求是给出点之一，所以直接组合这个点即可。将其还原到切比雪夫问题的坐标系，将得到的点((x,y))变为((x+y,x-y))即可，注意到得到的点的坐标可能不是整点，所以把周围的整点都算一遍取(min)就可以了。
- 关于精度问题， 同样可以采取在曼哈顿距离与切比雪夫距离的互化中介绍的策略，最后找点的时候再除以(2)。
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define R register
#define gc getchar
#define N 100010
using namespace std;
typedef long long ll;
ll n,x[N],y[N],sx[N],sy[N],ans=900000000000000000;
inline ll rd(){
ll x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
inline ll calc(ll nx,ll ny){
ll res=0;
for(R ll i=1;i<=n;++i) res+=max(abs(nx-x[i]),abs(ny-y[i]));
return res;
}
int main(){
n=rd();
for(R ll i=1;i<=n;++i){
x[i]=rd(); y[i]=rd();
sx[i]=x[i]+y[i]; sy[i]=x[i]-y[i];
}
sort(sx+1,sx+1+n);
sort(sy+1,sy+1+n);
ll ansx=((sx[(n+1)>>1]+sy[(n+1)>>1])>>1);
ll ansy=((sx[(n+1)>>1]-sy[(n+1)>>1])>>1);
for(R ll i=-1;i<=1;++i)
for(R ll j=-1;j<=1;++j) ans=min(ans,calc(ansx+i,ansy+j));
printf("%lld
",ans);
return 0;
}