总结

对于斜线移动的情况，即位置为 $(x, y)$ 的点可以跳跃到 $(x+1, y+1)$ 、 $(x+1, y-1)$ 、 $(x-1, y+1)$ 或 $(x-1, y-1)$ 。

为方便处理，我们旋转平面直角坐标系45°，同时以旋转后的$\frac{\sqrt2}{2}$格对标旋转前的$1$格

若旋转前坐标为$(X,Y)$，那么旋转后坐标$(x,y)=(X+Y,X-Y)$

可以发现旋转后的距离问题变成了曼哈顿距离：若两点的$x$的奇偶性相同则可以相互到达，$\text{dist}(A,B)=\frac{1}{2}(\lvert x_1-x_2\rvert+\lvert y_1-y_2\rvert)$，否则无法到达

E - Jump Distance Sum

地址

求解$\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j)$，直接做会存在绝对值的问题

正确的做法是先根据$x,y$与它们的奇偶性分为四组，对于每一组升序排序后求贡献

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void SINGLE_TEST()
{
    int n;cin>>n;
    vector<int> x(n+1),y(n+1);
    vector<vector<int>> g(4);
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        g[(x[i]+y[i])%2].push_back(x[i]+y[i]);
        g[2+(x[i]+y[i])%2].push_back(x[i]-y[i]);
    }

    for(int i=0;i<4;i++) sort(g[i].begin(),g[i].end());

    ll ans=0;
    for(int loc=0;loc<4;loc++){
        int siz=g[loc].size();
        for(int i=0;i<siz;i++){
            ans+=(i-(siz-i-1))*g[loc][i];
        }
    }
    cout<<ans/2<<'\n';
}

平面直角坐标系的斜线移动

及多点的曼哈顿距离的处理

总结

E - Jump Distance Sum