曼哈顿距离与切比雪夫距离

前言

之前在杂谈更过一篇曼哈顿距离的题，昨天的abcE考到了切比雪夫距离。这两个关系比较密切，总结一些

基本性质

曼哈顿距离

两点横轴坐标差的绝对值和$|x_2-x_1|+|y_2-y_1|$

应用在网格图最短路（只能上下左右移动）

切比雪夫距离

两点横轴坐标差的绝对值的最小值$min(|x_2-x_1|,|y_2-y_1|)$

应用在棋盘图（8个方向移动）

如果只能向4个方向移动，可以看下面的进阶

推论

常用距离算法详解 - 洛谷专栏 (luogu.com)

给出 曼哈顿 意义下的坐标 (𝑥,𝑦)，可转化成 切比雪夫 意义下的坐标 (𝑥+𝑦,𝑥−𝑦)。

反过来，我们也能通过 切比雪夫 意义下的坐标 (𝑥,𝑦) 转化为 曼哈顿 意义下的$(\frac{x+y}{2},\frac{x-y}{2})$
求曼哈顿距离可以转换为max(abs(x1 + y1 - x2 - y2,) abs(x1 - y1 - x2 + y2))也就是切比雪夫距离，预处理出所有x+y和x-y，直接max（最大的x+y - 最小的x+y, 最大的x-y - 最小的x-y)就可以得到最大曼哈顿距离了

这题比较进阶，稍微变式（奇偶性分组）

E - Jump Distance Sum (atcoder.jp)

#include<bits/stdc++.h>
#define endl '\n'
using ll = long long;
using namespace std;

int main(){
    ll n;
    cin>>n;
    vector<ll>v[4];
    for(int i = 0; i < n; i++){
        ll a,b; 
        cin>>a>>b;
        if((a+b) % 2){
            v[0].push_back(a+b);
            v[1].push_back(a-b);
        }else{
            v[2].push_back(a+b);
            v[3].push_back(a-b);
        }
    }
    ll ans = 0;
    for(int i = 0; i < 4; i++){
        sort(v[i].begin(), v[i].end());
        int sz = v[i].size();
        for(int j = 0; j < sz; j++){
            ans += v[i][j] * (2 * j + 1 - sz);
        }
    }
    cout<<ans/2<<endl;
    return 0;
}