AT_abc351_e [ABC351E] Jump Distance Sum

在坐标平面上有 $N$ 个点 $P_1,P_2,\ldots,P_N$，其中点 $P_i$ 的坐标为 $(X_i,Y_i)$。 对于两个点 $A,B$，定义它们的距离 $\text{dist}(A,B)$ 如下： > 一开始，兔子在点 $A$。 > 兔子如果在 $(x,y)$，则可以通过一次跳跃移动到 $(x+1,y+1)$、$(x+1,y-1)$、$(x-1,y+1)$ 或 $(x-1,y-1)$ 中的任意一个点。 > 从点 $A$ 移动到点 $B$ 所需的最少跳跃次数，定义为 $\text{dist}(A,B)$。 > 但是，如果无论跳多少次都无法从 $A$ 到达 $B$，则定义 $\text{dist}(A,B)=0$。 请计算 $\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N\ \text{dist}(P_i,P_j)$ 的值。

输入以如下格式从标准输入读入： > $N$ > $X_1$ $Y_1$ > $X_2$ $Y_2$ > $\vdots$ > $X_N$ $Y_N$

请输出 $\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N\ \text{dist}(P_i,P_j)$ 的值（整数）。

## 限制条件 - $2\leq N\leq 2\times 10^5$ - $0\leq X_i,Y_i\leq 10^8$ - 若 $i\neq j$，则 $(X_i,Y_i)\neq (X_j,Y_j)$ - 所有输入均为整数 ## 样例解释 1 $P_1,P_2,P_3$ 的坐标分别为 $(0,0)$、$(1,3)$、$(5,6)$。 从 $P_1$ 到 $P_2$，兔子可以按 $(0,0)\to (1,1)\to (0,2)\to (1,3)$ 跳跃，共需 $3$ 次，且无法用 $2$ 次或更少跳到，因此 $\text{dist}(P_1,P_2)=3$。 从 $P_1$ 到 $P_3$ 以及从 $P_2$ 到 $P_3$，兔子无法到达，因此 $\text{dist}(P_1,P_3)=\text{dist}(P_2,P_3)=0$。 所以，答案为 $\displaystyle\sum_{i=1}^{2}\displaystyle\sum_{j=i+1}^3\text{dist}(P_i,P_j)=\text{dist}(P_1,P_2)+\text{dist}(P_1,P_3)+\text{dist}(P_2,P_3)=3+0+0=3$。 由 ChatGPT 4.1 翻译