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)$ 的值（整数）。

输入输出样例 #1

输入 #1

3
0 0
1 3
5 6

输出 #1

3

输入输出样例 #2

输入 #2

5
0 5
1 7
2 9
3 8
4 6

输出 #2

11

说明/提示

限制条件

• $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 翻译