AtCoder ABC #178 : E - Dist Max

いろいろ遠回りしてしまった。
https://atcoder.jp/contests/abc178/tasks/abc178_e

問題

2次元座標上でN個の点の座標が与えられる。
2点のマンハッタン距離の最大値を求めよ。

解法

(X[i]+Y[i])の差の最大値か(X[i]-Y[i])の差の最大値を求めればよい。
そこで、(X[i]+Y[i])の最大最小値と、(X[i]-Y[i])の最大最小値を求めて、それぞれの差の大きい方を取ろう。

int N;
ll X[202020],Y[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	ll maP=-1LL<<60,miP=1LL<<60;
	ll maN=-1LL<<60,miN=1LL<<60;
	
	
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		maP=max(maP,X[i]+Y[i]);
		miP=min(miP,X[i]+Y[i]);
		maN=max(maN,X[i]-Y[i]);
		miN=min(miN,X[i]-Y[i]);
	}
	
	cout<<max(maP-miP,maN-miN)<<endl;
	
	
}

まとめ

本番SegTreeを使ってしまい反省。