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

問題へのリンク

問題概要

二次元平面上に $N$ 個の点 $(x_{i}, y_{i})$ がある。

これらのうちの 2 点のマンハッタン距離として考えられる最大値を求めよ。

制約

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

考えたこと

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

最遠な 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;
}

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

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

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

問題概要

制約

考えたこと

式変形

コード