[AtCoder] ABC 178 E – Dist Max

2020年9月14日2020年12月13日

問題

方針

点 \( 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) \]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int x[N], y[N];
    int t[N], u[N];
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        t[i] = x[i] + y[i];
        u[i] = x[i] - y[i];
    }
    sort(t, t + N);
    sort(u, u + N);
    int v1 = max(t[N - 1] - t[0], u[N - 1] - u[0]);
    int v2 = max(t[N- 1] - u[0], u[N- 1] - t[0]);
    int ans = max(v1, 0);
    cout << ans << "\n";
    return 0;
}