欧式距离也称欧几里得距离,是最常见的距离度量,衡量的是多维空间中两个点之间的绝对距离,也就是我们直观的两点之间最短的直线距离。
在二维空间中,两个点 (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)}。
第一行包含一个正整数 n。
接下来有 n 行,第 i+1 行有 2 个整数 x,y 表示第 i 个点的坐标。
【样例解释】
点 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。