[AtCoder] ABC 178 E – Dist Max

問題

方針

点 \( i \) と点 \( j \) のマンハッタン距離を \( d(i, j) = |x_i – x_j| + |y_i – y_j|\) とすると、絶対値の外し方を考慮して、

\begin{eqnarray}
\max(x_i – x_j + y_i – y_j, x_i – x_j – (y_i – y_j), -(x_i- x_j) + y_i – y_j, -(x_i – x_j) – (y_i – y_j))\\
\end{eqnarray}

と表すことができます。上記を \( i, j \) について整理すると、

\[ \max(x_i + y_i – (x_j + y_j), x_i – y_i – (x_j – y_j), -(x_i – y_i) + x_j – y_j, -(x_i + y_i) + x_j + y_j)\]

となります。ここで、\( t_i = x_i + y_i , u_i = x_i – y_i\) とすると、

\[ d(i, j) = \max(t_i – t_j, u_i- u_j, t_i – u_j, -t_i + u_j)\]

となります。\( i \) と \( j \) が分離されているので、任意の \( i \neq j \) を満たす任意の \( t_i, t_j, u_i, u_j \) を選ぶことができます。ここで、\( a = \max(t_i), b = \min(t_i), c = \max(u_i), d = \min(u_i) \) とすると \( d(i, j) \) の最大値は次の \( 4 \) つの値を考えれば良いです。

\[ \max(d(i, j)) = \max(a – b, c – d, a – d, c – b) \]

となります。

コード