几何题一直不会搞 后来看懂了题解 自己懒得写了 直接交了别人的代码 显然让求的是 2*sigma{(xi-xj)^2+(yi-yj)^2} 所以把x和y 独立出来分别计算(自己想的时候莫名奇妙的给他加了一个根号去想两点之间的距离了。。然后死也想不出来了 我真是不能再2了) 现在考虑 sigma(xi-xj)^2 记sum为所有可能的点的个数 x的范围是 10^6 所以可以处理每一个x上有多少个点 记为F(x) 那么答案就是 sigma(x-y)^2*Fx*Fy=sigma((x^2+y^2-2xy)*Fx*Fy) (Fx的统计是先找到xmin 和 xmax 用一个指针扫一遍) 再考虑 sigma(x^2FxFy)= sigma(x^2Fx*sigma(Fy))=sum*sigma(x^2*Fx) 同理 sigma(y^2FyFx) 也是 sum*sigma(x^2*Fx) 然后 是 2xyFxFy 这东西因式分解一下变成了 sigma(x*Fx)*sigma(y*Fy)=sigma(x*Fx)^2 x^2Fx xFx sum 都是 o(n) 可以统计出来的 然后 算个总和 除掉 (sum)*(sum-1)/2 再然后 就没有然后了