原题链接

目标需求

$\displaystyle \sum_{i<j}^n[(x_i-x_j)^2+(y_i-y_j)^2]=\displaystyle \sum_{i<j}^n(x_i-x_j)^2+ \displaystyle \sum_{i<j}^n(y_i-y_j)^2$

拆开发现 $x,y$ 相互独立我们只研究 $x$ 的部分 $y$ 部分同理

$\displaystyle \sum_{i<j}^n(x_i-x_j)^2=\sum_{i<j}^n(x_i^2+x_j^2-2x_ix_j)$

分析

对于前两项平方和 $\displaystyle \sum_{i<j}^n(x_i^2+x_j^2)=\displaystyle \sum_i^n(n-1)x_i^2$

因为是求每两个数的距离和,那么对于任意一项 $x_i$ 需要和其他 $n-1$ 项进行配对

而 $x_i^2$ 在一组配对计算中有且仅有一个,则对于 $n-1$ 的配对中 $x_i^2$ 会被加上 $n-1$ 次

也就是说任意的 $x_i^2$ 都会出现且仅出现 $n-1$ 次,即 $\displaystyle \sum_{i<j}^n(x_i^2+x_j^2)=\displaystyle \sum_i^n(n-1)x_i^2$

对于最后一项 $\displaystyle \sum_{i<j}^n 2x_ix_j={(\displaystyle \sum_i^nx_i)}^2-\displaystyle \sum_i^nx_i^2$

$\displaystyle \sum_{i<j}^n2x_ix_j=\displaystyle \sum_{i<j}^n(x_ix_j+x_jx_i)=\displaystyle \sum_{i,j}^nx_ix_j$

不考虑顺序的话任意的配对了无论是 $x_ix_j$ 还是 $x_jx_i$ 都会被计算一次

$\displaystyle \sum_{i,j}^nx_ix_j=(x_1+x_2+\dots+x_n)^2-x_1^2-x_2^2-\cdots x_n^2={(\displaystyle \sum_i^nx_i)}^2-\displaystyle \sum_i^nx_i^2$

将上述平方拆开就可以得到答案

别忘了这是 $2x_iy_i$ 后面计算别忘了负号

结果

$\displaystyle \sum_{i<j}^n(x_i-x_j)^2=\displaystyle \sum_i^n(n-1)x_i^2-\bigg[{(\displaystyle \sum_i^nx_i)}^2-\displaystyle \sum_i^nx_i^2\bigg]=n \displaystyle \sum_i^nx_i^2+{(\displaystyle \sum_i^nx_i)}^2$

同理

$\displaystyle \sum_{i<j}^n(y_i-y_j)^2=\displaystyle \sum_i^n(n-1)y_i^2-\bigg[{(\displaystyle \sum_i^ny_i)}^2-\displaystyle \sum_i^ny_i^2\bigg]=n \displaystyle \sum_i^ny_i^2+{(\displaystyle \sum_i^ny_i)}^2$

总结

将上诉两者相加
$\displaystyle \sum_{i<j}^n[(x_i-x_j)^2+(y_i-y_j)^2]=n\displaystyle \sum_i^n(x_i^2+y_i^2)-{(\displaystyle \sum_i^nx_i)}^2-{(\displaystyle \sum_i^ny_i)}^2$

代码

代码中只需要三个变量

s各个横纵坐标的平方和

sx横坐标的和

sy纵坐标的和

注意数据很大要开Long Long

#include<iostream>
using namespace std;
typedef long long LL;
int n,x,y;
LL s,sx,sy;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        s+=x*x+y*y;
        sx+=x,sy+=y;
    }
    cout<<n*s-sx*sx-sy*sy<<endl;
    return 0;
}