わかってしまえば軽めの問題。
https://yukicoder.me/problems/no/2612
問題
2次元座標系においてN個の点が与えられる。
各点を3色で塗り分けたとき、同色の2点のマンハッタン距離がR以下であるようにしたい。
Rの最小値を求めよ。
解法
二分探索で求める。
マンハッタン距離の問題なので、まず座標系を45度回転しておく。
すると、N個の点を3つの軸に平行な正方形で覆う問題となる。
N個の点を覆う最小の長方形を考えると、1つの正方形はその4つの角のどこかに配置される。
よってそれらを総当たりしよう。
この状態でまだ残っている点について、同じく最小の長方形を考えると、残り2個の正方形の配置は左上-右下か、左下-右上の2択である。
合わせてこの8択を総当たりしよう。
int N; ll X[202020],Y[202020]; int ok(ll v, vector<pair<ll,ll>> V) { ll Xma=-1LL<<60; ll Xmi=1LL<<60; ll Yma=-1LL<<60; ll Ymi=1LL<<60; int i; FOR(i,N) { int n=0; FORR2(a,b,V) if(a<=X[i]&&X[i]<=a+v&&b<=Y[i]&&Y[i]<=b+v) n=1; if(n==0) { Xmi=min(Xmi,X[i]); Xma=max(Xma,X[i]-v); Ymi=min(Ymi,Y[i]); Yma=max(Yma,Y[i]-v); } } if(Xmi==1LL<<60) return 1; if(V.size()==3) return 0; if(V.size()==0) { V.push_back({Xmi,Ymi}); if(ok(v,V)) return 1; V.pop_back(); V.push_back({Xmi,Yma}); if(ok(v,V)) return 1; V.pop_back(); V.push_back({Xma,Ymi}); if(ok(v,V)) return 1; V.pop_back(); V.push_back({Xma,Yma}); if(ok(v,V)) return 1; V.pop_back(); } else { V.push_back({Xmi,Ymi}); V.push_back({Xma,Yma}); if(ok(v,V)) return 1; V.pop_back(); V.pop_back(); V.push_back({Xma,Ymi}); V.push_back({Xmi,Yma}); if(ok(v,V)) return 1; V.pop_back(); V.pop_back(); } return 0; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>x>>y; X[i]=x+y; Y[i]=x-y; } ll ret=(1LL<<31)-1; for(i=30;i>=0;i--) if(ok(ret-(1LL<<i),{})) ret-=1LL<<i; cout<<ret<<endl; }
まとめ
なるほど。