\(\\\)
给出\(N\)个整点的坐标，在坐标系中选择一个整点，使得这个整点到这\(N\)个点的切比雪夫距离之和最小。
- \(N\in [1,10^5]\)，\(x_i,y_i\in [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#include #include #include #include #include #include #define R register#define gc getchar#define N 100010using 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\n",ans); return 0;}