Problem2371--暑假提高组模拟测试卷五 T2 距离

2371: 暑假提高组模拟测试卷五 T2 距离

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:][下载测试数据]

Description

欧式距离也称欧几里得距离,是最常见的距离度量,衡量的是多维空间中两个点之间的绝对距离,也就是我们直观的两点之间最短的直线距离。

在二维空间中,两个点 (x_1,y_1) 和 (x_2,y_2) 的欧式距离为 d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}。

对于这个问题,小明早就会了,现在他不在满足求两点间的欧式距离。他想知道 n 个点之间所有点对之间距离的平方和。

形式化地说,现在给定 n 个点 (x_1,y_1),(x_2,y_2),.......,(x_n,y_n),需要求出 \sum{i=1}^{n}\sum{j=i+1}^{n}{((x_i-x_j)^2+(y_i-y_j)^2)}。





Input

第一行包含一个正整数 n。

接下来有 n 行,第 i+1 行有 2 个整数 x,y 表示第 i 个点的坐标。



Output

输出一行一个整数,表示所有点对之间距离的平方和。

Sample Input

4
1 1
-1 -1
1 -1
-1 1

Sample Output

32

HINT

【样例解释】

点 1 和点 2 的距离平方为 2^2+2^2=8;

点 1 和点 3 的距离平方为 0^2+2^2=4;

点 1 和点 4 的距离平方为 2^2+0^2=4;

点 2 和点 3 的距离平方为 2^2+0^2=4;

点 2 和点 4 的距离平方为 0^2+2^2=4;

点 3 和点 4 的距离平方为 2^2+2^2=8;

综上,所有点对的距离平方和为 8+4+4+4+4+8=32。

【数据范围】

对于 40% 的数据,2< n < 5000,并且对于每一个点的坐标, |x|< 10^4,|y| < 10^4;

对于 80% 的数据,2< n < 10^5,并且对于每一个点的坐标, |x|< 10^4,|y| < 10^4;

对于 100% 的数据,2< n < 10^5,并且对于每一个点的坐标,有 |x| < 10^5,|y| < 10^5。



Source/Category

 

[Submit] [Status]