HDU 4312 Meeting Point：切比雪夫距離轉曼哈頓距離的幾何技巧

題目大意

給定平面上 n ≤ 10⁵ 個點，選一個點作為集合點，使所有點到該點的切比雪夫距離之和最小。切比雪夫距離：D((x1,y1),(x2,y2)) = max(|x1-x2|, |y1-y2|)。

幾何變換：45° 旋轉 + 縮放

令新坐標：

u = x + y
v = x - y

則 max(|x1-x2|, |y1-y2|) = (|u1-u2| + |v1-v2|) / 2。
即切比雪夫距離 = 旋轉 45° 並縮放 √2 後的曼哈頓距離 / 2。

問題轉化

在 (u, v) 坐標系中，尋找一點使曼哈頓距離和最小。對於曼哈頓距離，最優點的 u 坐標是所有 u_i 的中位數，v 同理。但本題要求集合點必須是原點集中的點，故需在原點中枚舉最優點。

O(n log n) 算法

1. 計算所有點的 u = x+y, v = x-y。
2. 按 u 排序，預處理前綴和 prefU[i]，可 O(1) 算出任意點作為集合點時的 u 方向距離和：
   sumU = u[i]*i - prefU[i-1] + (prefU[n]-prefU[i]) - u[i]*(n-i)。
3. 同理按 v 排序計算 sumV。
4. 枚舉每個原始點，總距離 = (sumU + sumV) / 2，取最小值。

C++ 代碼

#include 
using namespace std;
typedef long long LL;
struct Pt { LL x, y, u, v, sum; } p[100010];
LL pre[100010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> p[i].x >> p[i].y;
            p[i].u = p[i].x + p[i].y;
            p[i].v = p[i].x - p[i].y;
            p[i].sum = 0;
        }
        // u 方向
        sort(p+1, p+n+1, [](Pt a, Pt b){ return a.u < b.u; });
        for (int i = 1; i <= n; ++i) pre[i] = pre[i-1] + p[i].u;
        for (int i = 1; i <= n; ++i) {
            p[i].sum += p[i].u * (i-1) - pre[i-1];
            p[i].sum += pre[n] - pre[i] - p[i].u * (n-i);
        }
        // v 方向
        sort(p+1, p+n+1, [](Pt a, Pt b){ return a.v < b.v; });
        for (int i = 1; i <= n; ++i) pre[i] = pre[i-1] + p[i].v;
        for (int i = 1; i <= n; ++i) {
            p[i].sum += p[i].v * (i-1) - pre[i-1];
            p[i].sum += pre[n] - pre[i] - p[i].v * (n-i);
        }
        LL ans = LLONG_MAX;
        for (int i = 1; i <= n; ++i) ans = min(ans, p[i].sum / 2);
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n log n)（兩次排序）。
• 空間：O(n)。

總結

本題展示了坐標變換將切比雪夫距離轉為曼哈頓距離的經典技巧，配合「中位數性質 + 前綴和快速計算距離和」，實現了 O(n log n) 最優解。同類技巧常見於 HDU 4311、Codeforces 幾何優化問題中。