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)$。
$\text{dist}(A, B)$ 定义为从点 $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)$ 的值，作为一个整数。

3
0 0
1 3
5 6

3

5
0 5
1 7
2 9
3 8
4 6

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)$ 所有输入值均为整数。$P_1$、$P_2$ 和 $P_3$ 的坐标分别为 $(0,0)$、$(1,3)$ 和 $(5,6)$。
兔子可以通过 $(0,0) \to (1,1) \to (0,2) \to (1,3)$ 在三次跳跃内从 $P_1$ 到达 $P_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$.

标签: AtCoder|abc351E

来源

AtCoder|abc351E