yukicoder : No.1998 Manhattan Restaurant

こちらも考え方はシンプル。
https://yukicoder.me/problems/no/1998

問題

2次元座標上にN個の座標が与えられる。
ここで2か所任意の場所を選び、点を追加したとする。
d(i)を、元のi番目の点から、追加した2点それぞれのマンハッタン距離のうち小さい方とする。
max(d(i))の最小値を求めよ。

解法

まずマンハッタン距離に関する問題の典型テクとして、各点の座標(x,y)を、(x+y,x-y)と変換しておく。
こうすると、この問題は「2つの同じ大きさの正方形で、N点を覆いたい。最小の大きさはなにか？」という問題になる。

大きさを二分探索することを考える。
2つの正方形の配置は以下の2択になる。

• 片方の正方形は、一番左の点を左端、一番下の点を下端にする。残りをもう1つの正方形で覆う。
• 片方の正方形は、一番右の点を右端、一番下の点を下端にする。残りをもう1つの正方形で覆う。

ll N;
ll X[101010],Y[101010];
vector<pair<ll,ll>> ev;
multiset<ll> X1,Y1,X2,Y2;

int ok(ll v) {
	
	ll miy=1LL<<60,mix=1LL<<60;
	int i;
	FOR(i,N) {
		miy=min(miy,Y[i]);
		mix=min(mix,X[i]);
	}
	ll L=1LL<<60,R=-1LL<<60;
	ll D=1LL<<60,U=-1LL<<60;
	FOR(i,N) {
		if(X[i]-mix<=v&&Y[i]-miy<=v) continue;
		L=min(L,X[i]);
		R=max(R,X[i]);
		D=min(D,Y[i]);
		U=max(U,Y[i]);
	}
	
	return ((R-L)<=v&&(U-D)<=v);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll xma=-1LL<<60,xmi=1LL<<60,yma=-1LL<<60,ymi=1LL<<60;
	FOR(i,N) {
		cin>>x>>y;
		X[i]=x+y;
		Y[i]=x-y;
		xma=max(xma,X[i]);
		xmi=min(xmi,X[i]);
		yma=max(yma,Y[i]);
		ymi=min(ymi,Y[i]);
	}
	
	if(N<=2) {
		cout<<0<<endl;
		return;
	}
	
	
	ll ret=(xma-xmi)+(yma-ymi);
	FOR(i,2) {
		ll can=1LL<<33;
		for(j=32;j>=0;j--) if(ok(can-(1LL<<j))) can-=1LL<<j;
		ret=min(ret,can);
		FOR(j,N) X[j]=-X[j];
	}
	cout<<ret/2<<endl;
	
}

まとめ

オーソドックスな問題だけど、過去出たことはないのかな？