分数: 500 点
问题陈述
在坐标平面上,有 N 点 P_1, P_2, \ldots, P_N,其中点 P_i 有坐标 (X_i, Y_i).
距离 \text{dist}(A, B) 两点之间 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).
约束
- 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)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
3 0 0 1 3 5 6
示例输出 1
3
P_1, P_2,和 P_3 有坐标 (0,0), (1,3),和 (5,6)。
兔子可以从 P_1 to P_2 三跳通过 (0,0) \to (1,1) \to (0,2) \to (1,3),但不是两次或更少的跳跃,
so \text{dist}(P_1, P_2) = 3.
兔子无法从 P_1 to P_3 或来自 P_2 to 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.
示例输入 2
5 0 5 1 7 2 9 3 8 4 6
示例输出 2
11