← 返回题目列表

AtCoder · abc351_e

H. 跳跃距离总和

中文机器翻译题面 查看原题

分数: 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