AtCoder Beginner Contest 178, E : Dist Max

問題文

　https://atcoder.jp/contests/abc178/tasks/abc178_e

問題概要

　二次元空間上に $N$ 個の点があり，$i$ 番目の点の座標は $( x_i, y_i )$ である．異なる 2 点の manhattan 距離の最大値はいくらか？

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq x_i, y_i \leq 10^9$

解法

　空間を $\frac \pi 8$ 回転させると，manhattan 距離が Chebyshev 距離 に変換されます．Chebyshev 距離では絶対値の和ではなく小さくない方をとって距離とするので，軸毎に独立となって性質がよくなります．回転させる方法としては 回転行列 に $\frac \pi 8$ を入れてあげればよくて，（$\sqrt 2$ 倍とかを無視すれば，）
\begin{align*}
x_i' &= x_i - y_i \\
y_i' &= x_i + y_i
\end{align*}
という風に変換してあげればよいです．
　この変換をやった後に，X' 座標と Y' 座標の最大値・最小値をそれぞれ求めてそれぞれ差をとったときに最大値をとる点対が答えの候補です．最後に元々の空間での距離を求めて出力すればよいです．
　この解法の計算量は，変換・最大/最小の計算などのパートが $\Theta( N )$ 時間で終わり，答えの計算などは $O( 1 )$ 時間なので，全体は $\Theta( N )$ 時間です．

コード

int main()
{
	IN( int, N );
	VI X( N ), Y( N );
	REP( i, N )
	{
		cin >> X[i] >> Y[i];
	}

	VI Xr( N ), Yr( N );
	REP( i, N )
	{
		Xr[i] = X[i] - Y[i];
		Yr[i] = X[i] + Y[i];
	}

	const auto min_x = min_element( ALL( Xr ) );
	const auto max_x = max_element( ALL( Xr ) );
	const auto min_y = min_element( ALL( Yr ) );
	const auto max_y = max_element( ALL( Yr ) );

	int ri = -1, rj = -1, r = 0;
	if ( chmax( r, *max_x - *min_x ) )
	{
		ri = min_x - begin( Xr );
		rj = max_x - begin( Xr );
	}
	if ( chmax( r, *max_y - *min_y ) )
	{
		ri = min_y - begin( Yr );
		rj = max_y - begin( Yr );
	}

	cout << abs( X[ ri ] - X[ rj ] ) + abs( Y[ ri ] - Y[ rj ] ) << endl;

	return 0;
}