跳跃距离之和

题目描述

在坐标平面上有 $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

$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$。

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)$
• 输入中的所有值均为整数。