题目描述
在一个坐标平面上,有 N 个点 P1,P2,…,PN,其中点 Pi 的坐标为 (Xi,Yi)。两点 A 和 B 之间的距离 dist(A,B) 定义如下:
遥远的她最初位于点 A。遥远的她在位置 (x,y) 可以跳到 (x+1,y+1), (x+1,y−1), (x−1,y+1) 或 (x−1,y−1) 中的一个点,完成一次跳跃。
dist(A,B) 定义为从点 A 到点 B 需要的最小跳跃次数。如果在任意次数的跳跃后无法从点 A 到达点 B,则令 dist(A,B)=0。
计算以下和:
$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \text{dist}(P_i, P_j)$
即任意两点距离之和。
输入格式
一行一个整数 N ,代表点的数量。
输出格式
接下来 N 行,每行两个整数 (Xi,Yi)
一行一个整数,表示答案
样例输入1
3
0 0
1 3
5 6
样例输出1
3
样例解释1
dist(1,2)=3,dist(2,3)=0,dist(1,3)=0
样例输入2
5
0 5
1 7
2 9
3 8
4 6
样例输出2
11
- 对于 60% 的数据,满足 N≤100