算法竞赛模板

Jump Distance Sum

转化后可以发现对于 $ x + y $ 为偶数的，只能跳到 $ x + y $ 为偶数的点上， 因为每次跳跃改变 $ x + y $ 的值只能为 $+2$, $-2$ 或 $0$
那对于 $ x + y $ 分奇偶求

观察发现这个最短距离等价于切比雪夫距离
$ \max( \vert x_1 - x_2 \vert, \vert y_1 - y_2 \vert ) $

那可以转换为曼哈顿距离, 点化为 $ (\frac{x+y}{2},\frac{x-y}{2}) $

然后用新的点算曼哈顿距离 $ \vert x_1 - x_2 \vert + \vert y_1 - y_2 \vert $

这样新的点在新的坐标系下的曼哈顿距离就是原来坐标系上的两点的切比雪夫距离

同理，原曼哈顿距离可以转为新的点 $ (x + y,x - y) $ 的切比雪夫距离

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

struct pt {
    int x, y;
};
vector<pt> odd(1), even(1);

int cal(vector<pt>& a) {
    int n = a.size() - 1;
    int res = 0;
    sort(a.begin()+1,a.end(),[](pt& c, pt& d) {return c.x < d.x;});
    vector<int> pre(n+1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i-1] + a[i].x; 
    }
    for (int i = 1; i <= n - 1; i++) {
        res += pre[n] - pre[i] - (n-i) * a[i].x;
    }
    sort(a.begin()+1,a.end(),[](pt& c, pt& d) {return c.y < d.y;});
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i-1] + a[i].y; 
    }
    for (int i = 1; i <= n - 1; i++) {
        res += pre[n] - pre[i] - (n-i) * a[i].y;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        if ((x + y) % 2 == 0) {
            even.push_back({(x+y)/2,(x-y)/2});
        } else {
            odd.push_back({(x+1+y)/2,(x+1-y)/2});
        }
    }
    cout << cal(even) + cal(odd);
    return 0;
}