💬

ABC 178 | E - Dist Max

2020/12/22に公開

競プロ

式展開

tech

問題

解法

$i,j$ の組み合わせにおいて $max (|x_i - x_y| + |y_i - y_j|)$ を求める問題である。
貪欲にやると $O(N^2)$ かかり $N \leq 2 \times 10^5$ よりTLEしてしまう。
絶対値内で $i, j$ が結びついているので $i, j$ をそれぞれ独立に計算できないか式展開をする。

$|a| = a または -a$ なので $|x_i-x_y| + |y_i-y_j|$ は以下に展開できる。

\begin{aligned} (x_i - x_j) + (y_i-y_j) &= (x_i + y_i) - (x_j + y_j) \\\\ (x_i - x_j) - (y_i-y_j) &= (x_i - y_i) - (x_j - y_j) \\\\ -(x_i - x_j) + (y_i-y_j) &= -(x_i - y_i) + (x_j - y_j) \\\\ -(x_i - x_j) - (y_i-y_j) &= -(x_i + y_i) + (x_j + y_j) \\\\ \end{aligned}

プラスの項は大きく、マイナスの項は小さくできればよい。 $i, j$ 独立に $x+y$ と $x-y$ を求めソートし、それぞれ最大から最小を引いて、その最大値を求めれば答えとなる。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  vector<int> x(n), y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  // xi + yiを格納
  vector<int> a(n);
  // xi - yiを格納
  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    a[i] = x[i] + y[i];
    b[i] = x[i] - y[i];
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  int ans = 0;
  ans = max(ans, a[n - 1] - a[0]);
  ans = max(ans, b[n - 1] - b[0]);

  cout << ans << endl;
}

マンハッタン距離について

とある点から距離3でいける点をプロットすると以下のようになる。

45度傾いた正方形の範囲内なら移動することができる。

とある点からとある点までの距離は上記のように表せて、 $max(a, b)$ が点間のマンハッタン距離になる。

45度傾いた座標系を扱えればマンハッタン距離を楽に扱える。

$(x, y)$ を45度傾けた座標を $(x', y')$ とすると以下になる。

\begin{pmatrix}x' \\ y'\end{pmatrix} = \dfrac{1}{\sqrt{2}} \begin{pmatrix}x - y \\ x + y\end{pmatrix}

これは解法ででてきた $x+y$ と $x-y$ である。 $\dfrac{1}{\sqrt{2}}$ を無視すると $max(|x_1' - x_2'|, |y_1' - y_2'|)$ を求めていたので45度傾けた座標で求めていたのと同じことだったのである。

ABC 178 | E - Dist Max

問題

解法

コード

マンハッタン距離について

参考

Discussion