题意：
给定n个点，求所有点对之间距离的平方和。
思路：
考虑每一个点的贡献，现在有两个点对u , v u,vu,v，距离的平方和为( x [ u ] − x [ v ] ) 2 + ( y [ u ] − y [ v ] 2 )。
单独看x，x [ u ] 2 + x [ v ] 2 − 2 ∗ x [ u ] ∗ x [ v ]；
对于u来说，贡献是x [ u ] 2 − 2 ∗ x [ u ] ∗ x [ v ]
一共有n − 1个( u , t )类型的点对，所以x [ u ] 2会出现n − 1次。
由于2 ∗ x [ u ] ∗ x [ v ]也算是v的贡献，为了避免重复，每次都只计算t > u t>ut>u时的贡献。
y yy同理。维护两个前缀和就好了
代码：
// Problem: E. Points // Contest: Codeforces - All-Ukrainian School Olympiad in Informatics // URL: https://codeforces.com/contest/76/problem/E // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=1e6+7; ll sumx[maxn],sumy[maxn]; PLL p[maxn]; int main(){ int n=read; rep(i,1,n){ p[i].first=read,p[i].second=read; sumx[i]=sumx[i-1]+p[i].first; sumy[i]=sumy[i-1]+p[i].second; } ll ans=0; rep(i,1,n){ ans=ans+(n-1)*p[i].first*p[i].first-2*p[i].first*(sumx[n]-sumx[i]); ans=ans+(n-1)*p[i].second*p[i].second-2*p[i].second*(sumy[n]-sumy[i]); } write(ans); return 0; }
