けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 178 E - Dist Max (緑色, 500 点)

これ!!!!!HUPC 2019 day2 セットで出したやつや!!!

問題概要

二次元平面上に  N 個の点  (x_{i}, y_{i}) がある。これらのうちの 2 点のマンハッタン距離として考えられる最大値を求めよ。

制約

  •  2 \le N \le 2 \times 10^{5}

考えたこと

2 点の位置関係としては、以下の 2 パターンがありうる。

f:id:drken1215:20201031191027p:plain

最遠な 2 点の位置関係について考えてみると...

  • 最遠な 2 点が、左のパターンだった場合は、 x_{i} + y_{i} の最大値  M_{1} と最小値  m_{1} との差
  • 最遠な 2 点が、右のパターンだった場合は、 x_{i} - y_{i} の最大値  M_{2} と最小値  m_{2} との差

が答えになる。よって直感的には

 \max(M_{1} - m_{1}, M_{2} - m_{2})

が答えになりそうだ。このことをもう少し式変形ベースで示してみる。

式変形

絶対値に関する問題では

 |x| = \max(x, -x)

を利用すると見通しがよくなることがよくある。各組  (i, j) に対して、 x_{i} \lt x_{j} であるとしても一般性を失わず (逆であれば swap すればよい)、

 |x_{i} - x_{j}| + |y_{i} - y_{j}|
 = (x_{j} - x_{i} + \max(y_{j} - y_{i}, y_{i} - y_{j}))
 = \max((x_{j} + y_{j}) - (x_{i} + y_{i}), (x_{j} - y_{j}) - (x_{i} - y_{i}) )

と式変形できる。よって、

  •  (i, j) についての  (x_{j} + y_{j}) - (x_{i} + y_{i}) の最大値
  •  (i, j) についての  (x_{j} - y_{j}) - (x_{i} - y_{i}) の最大値

のうちの大きい方が答えとなる。以上から、上述の

 \max(M_{1} - m_{1}, M_{2} - m_{2})

が答えになることが確かめられた。計算量は  O(N) となる。

コード

下のコードでは sort を使っているため、 O(N \log N) になっている。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> x(N), y(N), sum(N), sub(N);
    for (int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i];
        sum[i] = x[i] + y[i];
        sub[i] = x[i] - y[i];
    }
    sort(sum.begin(), sum.end());
    sort(sub.begin(), sub.end());
    cout << max(sum.back() - sum[0], sub.back() - sub[0]) << endl;
}