Khoảng cách Manhattan và phép xoay 45 độ

Khoảng cách Manhattan giữa hai điểm là $|x_1-x_2|+|y_1-y_2|$: số bước ngắn nhất để đi giữa hai ô trên lưới khi chỉ được đi lên, xuống, trái, phải. Trang này gom các kỹ thuật chuyên cho khoảng cách này. Kỹ thuật trung tâm là phép xoay 45 độ $u=x+y$, $v=x-y$, biến Manhattan thành khoảng cách Chebyshev $max(|du|,|dv|)$. Nhờ phép xoay, "hình thoi" trở thành hình vuông song song trục, và các bài như tính tổng trong hình thoi cho mọi tâm hay tìm cặp điểm xa nhất đều giải được trong $O(1)$ mỗi truy vấn hoặc $O(N)$ cho cả tập, thay vì $O(K^2)$ mỗi tâm hay $O(N^2)$ mọi cặp. Đây là một chủ đề con của hình học tính toán, nhưng gần như chỉ dùng số nguyên và không cần tích có hướng.

Ý tưởng / Trực giác

Ba cách đo khoảng cách trên lưới

Với độ lệch $dx=x_1-x_2$, $dy=y_1-y_2$:

"Hình tròn" ở cột cuối là tập các điểm cách tâm không quá $d$. Chính hình dạng của nó quyết định bài có dễ hay không: hình vuông song song trục là thứ ta xử lý giỏi nhất (tổng tiền tố 2D, quét, cây phân đoạn), còn hình thoi thì không.

Phép xoay 45 độ: Manhattan thành Chebyshev

Đặt $u=x+y$, $v=x-y$. Khi đó với mọi hai điểm:

$$|dx|+|dy|=max(|du|,|dv|),du=dx+dy,dv=dx-dy.$$

Chứng minh. Với hai số thực $a,b$ bất kỳ, $|a|+|b|$ là giá trị lớn nhất của $s·a+t·b$ khi $s,t\in \{-1,+1\}$ (chọn $s$ cùng dấu với $a$, $t$ cùng dấu với $b$). Bốn tổ hợp dấu cho bốn giá trị $a+b$, $-(a+b)$, $a-b$, $-(a-b)$, nên

$$|a|+|b|=max(a+b,-a-b,a-b,-a+b)=max(|a+b|,|a-b|).$$

Thay $a=dx$, $b=dy$ là xong. $∎$

Chiều ngược lại cũng đúng: $max(|dx|,|dy|)={\displaystyle \frac{|du|+|dv|}{2}}$, nên bài Chebyshev (quân vua) cũng xoay được về Manhattan. Phép biến đổi ngược là $x={\displaystyle \frac{u+v}{2}}$, $y={\displaystyle \frac{u-v}{2}}$.

Về hình học, $(x,y)\mapsto (x+y,x-y)$ là phép xoay ${45}^{\circ }$ kèm phóng to $\sqrt{2}$ lần (và một phép lật, không ảnh hưởng gì). Bốn cạnh của hình thoi nằm trên các đường $x+y=\text{const}$ và $x-y=\text{const}$, tức $u=\text{const}$ và $v=\text{const}$: sau khi đổi biến, chúng thành các cạnh song song trục.

Hình thoi thành hình vuông

Hình thoi tâm $(x_0,y_0)$ bán kính $d$ là $\{(x,y):|x-x_0|+|y-y_0|\le d\}$. Theo công thức trên, đó chính là

$$\{(u,v):|u-u_0|\le d,|v-v_0|\le d\},$$

một hình vuông cạnh $2d$ song song trục trong mặt phẳng $(u,v)$. Mọi công cụ cho hình chữ nhật dùng được ngay:

• Tổng trong hình thoi: dựng tổng tiền tố 2D trên lưới đã xoay, mỗi hình thoi là một truy vấn hình chữ nhật $O(1)$.
• Cặp điểm xa nhất: khoảng cách Chebyshev lớn nhất là $max(maxu-minu,maxv-minv)$, vì hai trục $u,v$ tách rời nhau trong phép lấy $max$.
• Đặt hình thoi phủ nhiều điểm nhất: thành đặt hình vuông, giải bằng sweep line và cây phân đoạn.

Tách trục: khi không cần xoay

Với tổng khoảng cách, không cần xoay: $\sum (|dx|+|dy|)=\sum |dx|+\sum |dy|$, mỗi trục là một bài một chiều độc lập. Hai bài một chiều kinh điển:

• Tổng $|a_i-a_j|$ trên mọi cặp: sau khi sắp xếp, $a_i$ đứng sau đúng $i$ phần tử không lớn hơn nó (chỉ số từ $0$), nên nó đóng góp $a_i·i-(a_0+\dots +a_{i-1})$. Một lần sắp xếp và một biến tiền tố là đủ, $O(N\log N)$.
• Điểm $p$ làm $\sum |a_i-p|$ nhỏ nhất là trung vị. Khi dịch $p$ sang phải một đơn vị, mọi điểm ở bên trái hoặc tại $p$ xa thêm $1$, mọi điểm ở bên phải hẳn gần lại $1$. Chừng nào số điểm ở bên phải hẳn còn nhiều hơn số điểm ở bên trái hoặc tại $p$ thì dịch tiếp còn có lợi; dừng lại đúng khi hai bên cân bằng, tức ở trung vị. Với $N$ chẵn, mọi $p$ nằm giữa hai phần tử giữa đều tối ưu như nhau.

Trong 2D, điểm gặp tối ưu (tổng khoảng cách Manhattan tới $N$ điểm nhỏ nhất) là $(\text{trung vị }x,\text{trung vị }y)$, vì hai trục độc lập. Lưu ý điểm này không nhất thiết là một trong $N$ điểm đã cho.

Ngược lại, max và min khoảng cách thì không tách trục được ($max(|dx|+|dy|)\ne max|dx|+max|dy|$, vì hai giá trị lớn nhất có thể đến từ hai cặp khác nhau). Đó là lúc cần phép xoay.

Ví dụ chạy tay

Xoay lưới $3\times 3$ và tính tổng trong hình thoi

Lưới $n=m=3$ (hàng $i$, cột $j$, đánh số từ $0$). Để chỉ số không âm, dùng $u=i+j$, $v=i-j+(m-1)$, cả hai nằm trong $[0,n+m-2]$, nên lưới xoay có kích thước $S\times S$ với $S=n+m-1=5$.

Lưới gốc (giá trị)          (u, v) của từng ô
   j=0 j=1 j=2               j=0     j=1     j=2
i=0  3   1   4        i=0  (0,2)   (1,1)   (2,0)
i=1  1   5   9        i=1  (1,3)   (2,2)   (3,1)
i=2  2   6   5        i=2  (2,4)   (3,3)   (4,2)

Lưới xoay S x S (dấu . là ô không ứng với ô nào, giá trị 0)
        v=0 v=1 v=2 v=3 v=4
  u=0    .   .   3   .   .
  u=1    .   1   .   1   .
  u=2    4   .   5   .   2
  u=3    .   9   .   6   .
  u=4    .   .   5   .   .

Lưới gốc "đứng trên một đỉnh" sau khi xoay; các ô thật chỉ nằm ở những vị trí có $u+v-(m-1)$ chẵn, các vị trí còn lại bằng $0$.

Truy vấn 1: hình thoi tâm $(1,1)$ (ô giá trị $5$), bán kính $1$. Tâm có $u_0=2$, $v_0=2$. Hình vuông $u\in [1,3]$, $v\in [1,3]$:

        v=0 v=1 v=2 v=3 v=4
  u=0    .   .   3   .   .
  u=1    . [ 1   .   1 ] .
  u=2    4 [ .   5   . ] 2      tổng = 1 + 1 + 5 + 9 + 6 = 22
  u=3    . [ 9   .   6 ] .
  u=4    .   .   5   .   .

Đúng bằng tổng năm ô $(0,1),(1,0),(1,1),(1,2),(2,1)$ của hình thoi. Hai ô $4$ và $2$ ở hàng $u=2$ bị loại vì chúng cách tâm $2$.

Truy vấn 2: tâm $(0,0)$ (ô góc, giá trị $3$), bán kính $2$. Tâm có $u_0=0$, $v_0=2$, hình vuông là $u\in [-2,2]$, $v\in [0,4]$. Phần nằm ngoài lưới xoay bị kẹp về $u\in [0,2]$, $v\in [0,4]$: tổng ba hàng đầu $=3+1+1+4+5+2=16$, đúng bằng tổng các ô có $i+j\le 2$.

Bốn điểm: cặp xa nhất, tổng khoảng cách, điểm gặp

Cho $A(1,1)$, $B(4,2)$, $C(2,5)$, $D(6,4)$.

 y
 5 . . C . . . .
 4 . . . . . . D
 3 . . . . . . .
 2 . . . . B . .
 1 . A . . . . .
   0 1 2 3 4 5 6  x

• Cặp xa nhất: $maxu-minu=10-2=8$ (cặp $A,D$), $maxv-minv=2-(-3)=5$ (cặp $C,B$ hoặc $C,D$). Đáp án $max(8,5)=8$. Kiểm tra: $d(A,D)=5+3=8$.

• Tổng khoảng cách mọi cặp: trục $x$ đã sắp là $1,2,4,6$:

  $i$	$a_i$	tiền tố trước	đóng góp $a_i·i-\text{tiền tố}$
  0	1	0	0
  1	2	1	1
  2	4	3	5
  3	6	7	11

  Tổng trục $x$ là $17$. Làm tương tự với trục $y$ ($1,2,4,5$) được $0+1+5+8=14$. Đáp án $17+14=31$. Kiểm tra bằng sáu cặp: $4+5+8+5+4+5=31$.

• Điểm gặp tối ưu: trung vị $x$ là bất kỳ giá trị nào trong $[2,4]$, trung vị $y$ trong $[2,4]$. Chọn $(2,2)$: tổng khoảng cách $=(1+2+0+4)+(1+0+3+2)=13$, và không điểm nguyên nào cho tổng nhỏ hơn.

Cài đặt

C++: tổng lớn nhất trong hình thoi bán kính $k$ (lưới xoay + tổng tiền tố 2D)

Đọc lưới $n\times m$ và $k$, in tổng lớn nhất của một hình thoi bán kính $k$ có tâm là một ô bất kỳ (hình thoi được phép tràn ra ngoài lưới, phần tràn không có giá trị). Giá trị trong lưới có thể âm.

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

int n, m, S;                 // grid n x m, rotated grid S x S, S = n + m - 1
vector<vector<ll>> P;        // P[u+1][v+1]: prefix sums on the rotated grid

// Sum over rotated cells with u in [u1, u2], v in [v1, v2], clamped to the grid.
ll rectSum(int u1, int v1, int u2, int v2) {
    u1 = max(u1, 0); v1 = max(v1, 0);
    u2 = min(u2, S - 1); v2 = min(v2, S - 1);
    if (u1 > u2 || v1 > v2) return 0;
    return P[u2 + 1][v2 + 1] - P[u1][v2 + 1] - P[u2 + 1][v1] + P[u1][v1];
}

// Sum of all cells (i, j) with |i - r| + |j - c| <= k.
ll diamondSum(int r, int c, int k) {
    int u = r + c, v = r - c + (m - 1);
    return rectSum(u - k, v - k, u + k, v + k);
}

int main() {
    int k;
    scanf("%d %d %d", &n, &m, &k);
    S = n + m - 1;
    P.assign(S + 1, vector<ll>(S + 1, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            ll g; scanf("%lld", &g);
            P[i + j + 1][i - j + (m - 1) + 1] = g;   // (u, v) = (i + j, i - j + m - 1)
        }
    for (int u = 1; u <= S; u++)            // standard 2D prefix sums
        for (int v = 1; v <= S; v++)
            P[u][v] += P[u - 1][v] + P[u][v - 1] - P[u - 1][v - 1];

    ll best = LLONG_MIN;                     // values may be negative
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            best = max(best, diamondSum(i, j, k));
    printf("%lld\n", best);
}

Nếu mỗi tâm có bán kính riêng (ví dụ bán kính lớn nhất thỏa một điều kiện), chỉ cần gọi diamondSum(i, j, r[i][j]); phần dựng lưới xoay giữ nguyên.

C++: các công thức trên tập điểm

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

// Max Manhattan distance over all pairs: max(max u - min u, max v - min v).
ll maxPairDist(const vector<ll>& x, const vector<ll>& y) {
    ll uMax = LLONG_MIN, uMin = LLONG_MAX, vMax = LLONG_MIN, vMin = LLONG_MAX;
    for (size_t i = 0; i < x.size(); i++) {
        ll u = x[i] + y[i], v = x[i] - y[i];
        uMax = max(uMax, u); uMin = min(uMin, u);
        vMax = max(vMax, v); vMin = min(vMin, v);
    }
    return max(uMax - uMin, vMax - vMin);
}

// Sum of |a_i - a_j| over all pairs i < j (one axis).
ll sumPairs1D(vector<ll> a) {
    sort(a.begin(), a.end());
    ll prefix = 0, total = 0;
    for (size_t i = 0; i < a.size(); i++) {
        total += a[i] * (ll)i - prefix;   // a[i] minus each of the i smaller values
        prefix += a[i];
    }
    return total;
}
ll sumPairDist(const vector<ll>& x, const vector<ll>& y) {
    return sumPairs1D(x) + sumPairs1D(y);  // axes are independent
}

// Point minimising total Manhattan distance: (median x, median y).
pair<ll, ll> bestMeetingPoint(vector<ll> x, vector<ll> y) {
    size_t mid = (x.size() - 1) / 2;
    nth_element(x.begin(), x.begin() + mid, x.end());
    nth_element(y.begin(), y.begin() + mid, y.end());
    return {x[mid], y[mid]};
}

// d dimensions: fix the sign of coordinate 0, try all 2^(d-1) sign patterns.
ll maxPairDistD(const vector<vector<ll>>& p) {
    int d = p[0].size();
    ll best = 0;
    for (int mask = 0; mask < (1 << (d - 1)); mask++) {
        ll hi = LLONG_MIN, lo = LLONG_MAX;
        for (auto& q : p) {
            ll s = q[0];
            for (int k = 1; k < d; k++) s += (mask >> (k - 1) & 1) ? -q[k] : q[k];
            hi = max(hi, s); lo = min(lo, s);
        }
        best = max(best, hi - lo);
    }
    return best;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<ll> x(n), y(n);
    for (int i = 0; i < n; i++) scanf("%lld %lld", &x[i], &y[i]);
    auto [mx, my] = bestMeetingPoint(x, y);
    printf("%lld %lld %lld %lld\n", maxPairDist(x, y), sumPairDist(x, y), mx, my);
}

Với bốn điểm ở ví dụ trên, chương trình in 8 31 2 2.

Python

import sys


def max_pair_dist(pts):
    # rotate: Manhattan becomes Chebyshev
    us = [x + y for x, y in pts]
    vs = [x - y for x, y in pts]
    return max(max(us) - min(us), max(vs) - min(vs))


def sum_pairs_1d(a):
    a = sorted(a)
    total = prefix = 0
    for i, val in enumerate(a):
        total += val * i - prefix
        prefix += val
    return total


def sum_pair_dist(pts):
    return sum_pairs_1d([x for x, _ in pts]) + sum_pairs_1d([y for _, y in pts])


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    pts = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)]
    print(max_pair_dist(pts), sum_pair_dist(pts))


main()

Python không lo tràn số, nhưng với $N$ cỡ ${10}^6$ nên đọc nhanh bằng sys.stdin.buffer như trên.

Độ phức tạp

Duyệt trâu tương ứng: tổng hình thoi bán kính $k$ tốn $O(k^2)$ mỗi tâm, tức $O(nm{k}^2)$ cho mọi tâm; cặp xa nhất và tổng mọi cặp tốn $O(N^2)$.

⚠️ Lỗi thường gặp

• Chỉ số âm trên lưới xoay. $v=i-j$ có thể âm (nhỏ nhất là $-(m-1)$). Phải cộng thêm một độ dời bất kỳ $\ge m-1$ (gọn nhất là đúng $m-1$), kèm tăng kích thước lưới xoay tương ứng nếu chọn độ dời lớn hơn, và dùng cùng độ dời ở cả lúc dựng lẫn lúc truy vấn. Lưu ý $n$ có thể nhỏ hơn $m-1$, nên cộng $n$ không phải lúc nào cũng đủ. Triệu chứng: truy cập ra ngoài mảng hoặc kết quả lệch chỉ ở các ô gần cạnh trái.
• Lưới xoay có kích thước sai. $u$ chạy tới $n+m-2$ nên lưới xoay có cạnh $n+m-1$, không phải $max(n,m)$ hay $n$. Với lưới vuông $n\times n$ thì cạnh là $2n-1$, bộ nhớ gấp khoảng bốn lần lưới gốc; $n=1000$ cho khoảng $4·{10}^6$ số long long, vẫn ổn, nhưng hãy tính trước.
• Lưới dẹt làm nổ bộ nhớ. Với $n=1$, $m={10}^5$, lưới gốc chỉ có ${10}^5$ ô nhưng lưới xoay có ${10}^{10}$ ô. Khi $n$ và $m$ chênh lệch lớn, thay bằng tổng tiền tố theo từng hàng: hình thoi giao mỗi hàng thành một đoạn, truy vấn $O(min(n,2k+1))$.
• Quên kẹp hình vuông vào lưới. Hình thoi ở gần biên có $u-k<0$ hoặc $v+k\ge S$. Không kẹp thì đọc ra ngoài mảng tiền tố. Nếu đề yêu cầu hình thoi nằm trọn trong lưới (như bài trại bò tót), phải giới hạn bán kính bởi khoảng cách tới biên, việc kẹp không thay cho điều kiện này.
• Khởi tạo đáp án max bằng $0$. Nếu lưới có giá trị âm, mọi tổng hình thoi có thể âm và best = 0 in ra $0$ sai. Ví dụ lưới $2\times 2$ gồm $-1,-2,-3,-4$ với $k=0$: đáp án đúng là $-1$. Khởi tạo bằng LLONG_MIN (như chương trình trên) hoặc bằng tổng của tâm đầu tiên; chỉ khi đề bảo đảm giá trị không âm thì mới được dùng $0$.
• Tính chẵn lẻ khi đổi ngược. Chỉ những $(u,v)$ có $u\equiv v\left(\mathrm{mod}2\right)$ mới ứng với điểm nguyên $(x,y)=(\frac{u+v}{2},\frac{u-v}{2})$. Nếu tìm được tâm tối ưu trong mặt phẳng $(u,v)$ mà $u+v$ lẻ, tâm thật có tọa độ nửa nguyên. Bài cho đặt tâm ở vị trí thực thì chấp nhận được; bài bắt tâm là ô lưới thì phải chỉ duyệt các $(u,v)$ đúng chẵn lẻ.
• Tràn số. Tọa độ tới ${10}^9$ thì $u=x+y$ tới $2·{10}^9$, vượt int. Tổng khoảng cách mọi cặp với $N={10}^5$ có thể tới cỡ $N^2·{10}^9/2\approx 5·{10}^{18}$, sát giới hạn long long; đề thường cho lấy modulo hoặc ràng buộc nhỏ hơn, hãy đọc kỹ.
• Tách trục cho bài max. ${max}_{i,j}(|dx|+|dy|)$ không bằng $max|dx|+max|dy|$. Với $A(0,0)$, $B(10,0)$, $C(5,10)$: cách sai cho $max|dx|+max|dy|=10+10=20$, nhưng ba cặp có khoảng cách $10$, $15$, $15$ nên đáp án đúng là $15$ (cặp có $|dx|$ lớn nhất và cặp có $|dy|$ lớn nhất là hai cặp khác nhau). Chỉ tổng mới tách trục được; max và min phải xoay.
• Nhầm trung bình với trung vị. Điểm làm tổng bình phương khoảng cách nhỏ nhất là trung bình cộng; với tổng khoảng cách Manhattan thì là trung vị. Dùng trung bình cho bài $L_1$ sai ngay cả trên ba điểm $0,0,9$.
• Dùng BFS khi không có vật cản. Trên lưới không vật cản, BFS 4 hướng từ một ô chỉ tính lại công thức $|dx|+|dy|$ với chi phí $O(nm)$. BFS đa nguồn thì khác: nó cho $min$ khoảng cách Manhattan tới tập nguồn gần nhất, thứ mà công thức đơn lẻ không cho. Ngược lại, có vật cản thì khoảng cách thật luôn $\ge |dx|+|dy|$ và có thể lớn hơn hẳn, nên mọi công thức trên trang này không còn dùng được.

Biến thể / Mở rộng

Không gian $d$ chiều: $2^{d-1}$ bộ dấu

Tổng quát của chứng minh ở trên: ${\sum }_k|a_k|={max}_{s\in \{\pm 1{\}}^d}{\sum }_k{s}_k{a}_k$. Vậy

$${max}_{i,j}{d}_1(p_i,p_j)={max}_s({max}_i⟨s,p_i⟩-{min}_i⟨s,p_i⟩).$$

Bộ dấu $s$ và $-s$ cho cùng hiệu $max-min$, nên chỉ cần cố định $s_0=+1$ và thử $2^{d-1}$ bộ còn lại (hàm maxPairDistD ở trên). Với $d=2$ đó chính là hai trục $u=x+y$ và $v=x-y$. Khi $d\le 5$ hoặc $6$, cách này nhanh hơn nhiều so với $O(N^{2}d)$.

Điểm xa nhất tính từ một điểm truy vấn

Với điểm truy vấn $q$ có $(u_q,v_q)$, khoảng cách Manhattan lớn nhất tới tập điểm là

$$max(u_q-minu,maxu-u_q,v_q-minv,maxv-v_q).$$

Chỉ cần lưu bốn giá trị cực trị, mỗi truy vấn $O(1)$. Nếu tập điểm có thêm, xóa thì lưu $u$ và $v$ trong hai multiset.

Khoảng cách Chebyshev và bài quân vua

Số nước đi ít nhất của quân vua là $max(|dx|,|dy|)$: đi chéo $min(|dx|,|dy|)$ bước, rồi đi thẳng phần còn lại. Tổng khoảng cách Chebyshev mọi cặp tính được bằng cách xoay ngược: $max(|dx|,|dy|)=\frac{|du|+|dv|}{2}$, rồi tách trục $u$, $v$ như bài tổng Manhattan.

BFS trên lưới 4 hướng

Trên lưới không có vật cản, BFS 4 hướng từ ô $s$ cho đúng $d(s,t)=|dx|+|dy|$, BFS 8 hướng cho khoảng cách Chebyshev. BFS đa nguồn từ tập $T$ cho mỗi ô giá trị ${min}_{t\in T}{d}_1(·,t)$ trong $O(nm)$, hữu ích khi cần "bán kính lớn nhất trước khi hình thoi chạm vào một ô xấu". Kết hợp với lưới xoay: BFS cho bán kính, tổng tiền tố trên lưới xoay cho tổng trong hình thoi.

Hình thoi tâm tùy ý: đặt hình vuông phủ nhiều điểm nhất

Khi tâm được đặt ở vị trí thực bất kỳ, bài "hình thoi bán kính $K$ chứa tổng trọng số lớn nhất" thành "hình vuông cạnh $2K$ song song trục chứa tổng lớn nhất" trong mặt phẳng $(u,v)$. Đó là bài sweep line kinh điển: mỗi điểm $(u,v)$ tạo ra khoảng vị trí góc hình vuông mà nó được phủ, quét theo $u$ với cửa sổ độ rộng $2K$, dùng cây phân đoạn cộng đoạn, lấy max theo $v$ (tọa độ $v$ cần nén).

Cây khung nhỏ nhất Manhattan (MST Manhattan)

Đồ thị đầy đủ trên $N$ điểm với trọng số Manhattan có $\Theta (N^2)$ cạnh, quá nhiều khi $N={10}^5$. Tính chất then chốt: chia mặt phẳng quanh điểm $p$ thành 8 góc ${45}^{\circ }$ (tám góc phần tám). Nếu $q$ và $r$ cùng nằm trong một góc của $p$ và $q$ gần $p$ hơn thì $d(q,r)\le d(p,r)$, nên cạnh $(p,r)$ là cạnh nặng nhất trên chu trình $p,q,r$ và có thể bỏ. Vậy mỗi điểm chỉ cần nối với điểm gần nhất trong mỗi góc, tổng cộng không quá $8N$ cạnh ứng viên (do đối xứng, xét $4$ góc là đủ, còn $4N$ cạnh).

Điểm gần nhất trong một góc tìm được cho mọi điểm bằng một lượt quét: sắp theo một tọa độ, duy trì cây Fenwick trên $y-x$ (đã nén) lưu điểm có $x+y$ nhỏ nhất. Lặp lại với $4$ phép biến đổi tọa độ (đổi chỗ $x,y$ và đổi dấu $x$), rồi chạy Kruskal trên $O(N)$ cạnh. Tổng $O(N\log N)$. Phần Kruskal và các tính chất cây khung xem ở cây khung nhỏ nhất.

Cặp điểm gần nhất theo Manhattan

Bài cặp điểm gần nhất với khoảng cách Manhattan chạy trực tiếp được bằng khung chia để trị chuẩn, không cần xoay: với $d$ là đáp án tốt nhất hiện tại, trong dải chỉ giữ các điểm có $|dx|<d$ so với đường chia, rồi mỗi điểm chỉ so với các điểm có $|dy|<d$ (hình vuông này bao trọn hình thoi bán kính $d$, nên không bỏ sót cặp nào). Nếu muốn, có thể xoay sang Chebyshev để lọc chính xác: sau khi xoay, "hình tròn" láng giềng đã là hình vuông song song trục, nên phép lọc theo từng trục không còn giữ lại điểm thừa ở các góc.

"Nằm giữa" theo Manhattan

$d(p,r)=d(p,q)+d(q,r)$ khi và chỉ khi $q$ nằm trong hình chữ nhật bao của $p$ và $r$ (tức $q_x$ nằm giữa $p_x,r_x$ và $q_y$ nằm giữa $p_y,r_y$), vì đẳng thức phải xảy ra trên từng trục. Khác với Euclid (chỉ đúng khi $q$ nằm trên đoạn thẳng $pr$), tập các điểm "nằm giữa" theo Manhattan là cả một hình chữ nhật, và giữa hai điểm có rất nhiều đường đi ngắn nhất. Tính chất này hay dùng để đếm đường đi ngắn nhất trên lưới hoặc để nhận ra cấu trúc đơn điệu ẩn trong đề.

Bài tập luyện

Luyện kỹ thuật

• Đường đi ngắn nhất của vua (kingpath) (Nghiệp dư) số nước đi ít nhất của quân vua là khoảng cách Chebyshev $max(|dx|,|dy|)$; in đường đi bằng cách đi chéo trước rồi đi thẳng.
• Bò Lười (Silver) (lazycows) (Trung cấp) tổng lớn nhất trong hình thoi bán kính $K$ trên lưới $N\times N$: cùng bài toán với chương trình lưới xoay ở trên (lưới xoay cạnh $2N-1$), nhưng phải sửa phần đọc input vì đề cho N K rồi lưới $N\times N$, còn chương trình đọc n m k: đọc $n$, $k$ rồi đặt $m=n$.
• Dãy con Manhattan (manhsub) (Nâng cao) dùng tính chất "nằm giữa" theo Manhattan: bộ ba xấu với các điểm $(a_i,i)$ chính là ba phần tử tạo thành dãy con đơn điệu không chặt (không giảm hoặc không tăng, vì giá trị bằng nhau cũng xấu), từ đó suy ra đoạn tốt rất ngắn.
• Bò Lười (Gold) (lazycowg) (Kỳ cựu) tâm được đặt tùy ý: xoay 45 độ để hình thoi thành hình vuông cạnh $2K$, rồi tìm vị trí hình vuông phủ tổng lớn nhất bằng quét cửa sổ theo $u$ và cây phân đoạn theo $v$.
• Tam Giác Đều Manhattan (triangles) (Bậc thầy) sau khi xoay, trong mọi tam giác đều Manhattan luôn có hai đỉnh cùng $u$ hoặc cùng $v$; cố định cặp đó rồi đếm đỉnh thứ ba bằng tổng tiền tố dọc các đường chéo.

Đề VOI

• Trại bò tót (voi16_rbull) (Kỳ cựu) VOI 2016: với tâm cố định, bán kính càng lớn thì càng dễ vi phạm, nên mỗi tâm chỉ cần bán kính hợp lệ lớn nhất; hãy nghĩ xem bán kính đó liên hệ thế nào với khoảng cách Manhattan tới "những cọc gây rắc rối" (tính cho mọi ô cùng lúc), còn việc đếm cọc trong hình thoi là truy vấn hình vuông trên lưới xoay.
• Kết nối internet (voi22_inet) (Kỳ cựu) VOI 2022: hãy nghĩ tới cây khung nhỏ nhất của đồ thị đầy đủ với trọng số là khoảng cách Manhattan; đồ thị này có $\Theta (n^2)$ cạnh nên cần cách giảm số cạnh ứng viên như ở mục MST Manhattan phía trên.
• Năng lượng tối thiểu (voi23_robot) (Chuyên gia) VOI 2023: kỹ thuật trên trang này chỉ là một phần của lời giải. Số bước trên sân không vật cản chính là khoảng cách Manhattan (BFS đa nguồn chỉ đủ cho subtask sân ngắn); cố định dòng rồi tách $|r-r^{\prime }|+|c-c^{\prime }|$ thành phần theo dòng cộng phần tuyến tính theo cột, phần khó còn lại là cập nhật cục bộ khi thêm, bớt trạm.