AtCoder Beginner Contest 351 E - Jump Distance Sum

题目链接
Hint1: 只能斜着走，容易想到黑白棋盘，\((x+y)\%2==0\)位于一个团，\((x+y)\%2==1\)位于另一个团，分别求和。
Hint2: \(dist=max(|x1-x2|,|y1-y2|)\)，这是切比雪夫距离，将坐标系倾斜\(45^{\circ}\)，改为曼哈顿距离\(dist=|x1-x2|+|y1-y2|\)，即\(X=x+y,Y=x-y\)，这样就可以将横纵坐标分开计算，最终结果减半

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
//#define int long long
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int base = 131;
const int inf = INT_MAX;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int> > v1, v2;
    for (int i = 0, x, y; i < n; i++) {
        cin >> x >> y;
        if ((x + y) % 2) {
            v1.push_back({x, y});
        }
        else {
            v2.push_back({x, y});
        }
    }
    auto calc = [](vector<pair<int, int> > v) {
        int len = v.size();
        vector<int> a(len), b(len);
        for (int i = 0; i < len; i++) {
            a[i] = v[i].first + v[i].second;
            b[i] = v[i].first - v[i].second;
        }
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        ll cnt = 0, sum = 0, pre;
        for (int i = 0; i < len; i++) {
            if (i == 0) {
                pre = a[i];
                continue;
            }
            cnt += sum + i * (a[i] - pre);
            sum += i * (a[i] - pre);
            pre = a[i];
        }
        sum = 0;
        for (int i = 0; i < len; i++) {
            if (i == 0) {
                pre = b[i];
                continue;
            }
            cnt += sum + i * (b[i] - pre);
            sum += i * (b[i] - pre);
            pre = b[i];
        }
        return cnt;
    };
    cout << (calc(v1) + calc(v2)) / 2 << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}