マンハッタン距離の変換(典型36 Max Manhattan Distance)

典型90問楽しい。

前にも似た問題を解いた記憶があったので、45度変換 $(x,y)=>(x-y,x+y)$ を使ってすんなり解けたが、そういえばなんでその原理で解けるのか記憶が薄れていたので復習がてらまとめておく。

マンハッタン距離からチェビシェフ距離への変換

２次元座標系の2点 $(x_a,y_a),(x_b,y_b)$ を考える。
このときマンハッタン距離は下記の式で表される。

$D_{manhattan}=|x_a-x_b|+|y_a-y_b|$
この時、絶対値を取る演算が
$|v|=max(-v,v)$
のように、最大値を取る演算で置き換えられることを用いると、 $D_{manhattan}$ は以下のように変形できる。
$\begin{align} D_{manhattan}=max(x_a-x_b+y_a-y_b,x_a-x_b-(y_a-y_b),-(x_a-x_b)+y_a-y_b,-(x_a-x_b)-(y_a-y_b)) \end{align}$
更にこの式を、点a,bそれぞれ毎の変数でまとめると以下のようになる。
$\begin{align} D_{manhattan}&=max(x_a+y_a-(x_b+y_b),x_a-y_a-(x_b-y_b),-(x_a-y_a)+(x_b-y_b),-(x_a+y_a+(x_b+y_b)) \end{align}$
このようにまとめると、 $x+y,x-y$ で式全体が構成されていることがわかる。
この時 $x'=x-y,y'=x+y$ とおき、先程の式に代入してみると
$\begin{align} D_{manhattan}&=max(y'_a-y'_b,x'_a-x'_b,-x'_a+x'_b,-y'_a+y'_b)\\ &=max(|x'_a-x'_b|,|y'_a-y'_b|) \end{align}$
となる。このように変形することで、x軸の絶対値とy軸の絶対値をそれぞれ独立に計算し、その最大値を取れば良いという演算になり、問題によってはかなり有用な性質となる。
また、このように軸毎の距離の最大値を取るような距離尺度のことをチェビシェフ距離と呼ぶ。（チェスの動かし方のアレ）
ja.wikipedia.org

典型36での応用

今回の典型問題36を通常のマンハッタン距離の演算式で解こうとすると、
2点の全組み合わせについて $D_{manhattan}$ を計算する必要があり $O(N^2)$ となり間に合わない。
そこで先程のような座標変形 $x'=x-y,y'=x+y$ を行う。すると、ある点から見て各軸毎の最も遠い点が分かればあとはその最大を取れば良いことが分かる。
更に、最も遠い点は必ず各軸の両端のいずれかになる。よって、事前に $N$ 個の点の中でのx軸方向での最小、最大値、y軸方向での最小、最大値さえ求めておけば、ある点から見て最も遠い点の探索自体は下記の式で $O(1)$ で解ける。

$\begin{align} D_{max}=max(|x'-x'_{max}|,|x'-x'_{min}|,|y'-y'_{max}|,|y'-y'_{min}|) \end{align})$
よって、この問題は事前準備の最小、最大値の探索に $O(N)$ かかるので、全体 $O(N)$ で解ける。(正確には $N,Q$ のうち小さい方に依存するので $O(min(N,Q))$ ???記法がわからない...)

実装

#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define rreps(i, n, s) for (int i = s; i >= n; i--)

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, q;
    cin >> n >> q;
    vector<ll> xs(n), ys(n);
    rep(i, n) {
        ll x, y;
        cin >> x >> y;
        xs[i] = x - y;
        ys[i] = x + y;
    }
    ll min_x = *min_element(xs.begin(), xs.end());
    ll max_x = *max_element(xs.begin(), xs.end());
    ll min_y = *min_element(ys.begin(), ys.end());
    ll max_y = *max_element(ys.begin(), ys.end());
    rep(i, q) {
        int j;
        cin >> j;
        j--;
        ll res = max(max(abs(xs[j] - min_x), abs(xs[j] - max_x)), max(abs(ys[j] - min_y), abs(ys[j] - max_y)));
        cout << res << endl;
    }
    return 0;
}