CF76E Points 题解

题目大意

给出 n n n 个点的坐标 x x x 和 y y y，让你求出各个点的距离的平方和。

解法

两点距离公式： ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} (x1​−x2​)2+(y1​−y2​)2 ​。

本题是一道数学题，第一反应是枚举 ∑ i = 1 n ∑ j = i + 1 n ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 \sum\limits_{i=1}^n \sum\limits_{j=i+1}^n (x_1-x_2)^2+(y_1-y_2)^2 i=1∑n​j=i+1∑n​(x1​−x2​)2+(y1​−y2​)2，时间复杂度为 O ( n 2 ) O(n^2) O(n2)（跑不满），会超时，所以我们要对原式进行化简。

化简得 ( n − 1 ) × ∑ i = 1 n ( x i 2 + y i 2 ) − 2 × ( ∑ i = 1 n − 1 x i × ∑ j = i + 1 n x j + ∑ i = 1 n − 1 y i × ∑ j = i + 1 n y j ) (n-1) \times \sum\limits_{i=1}^n (x_i^2 + y_i^2)-2 \times (\sum\limits_{i=1}^{n-1}x_i \times \sum\limits_{j=i+1}^n x_j + \sum\limits_{i=1}^{n-1}y_i \times \sum\limits_{j=i+1}^n y_j) (n−1)×i=1∑n​(xi2​+yi2​)−2×(i=1∑n−1​xi​×j=i+1∑n​xj​+i=1∑n−1​yi​×j=i+1∑n​yj​)。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,ans1,sum1,sum2,ans2;
struct node
{
	int x,y;
	node()
	{
		x=0,y=0;
	}
	void init1()
	{
		ans1+=(long long)(x*x*(n-1))+(long long)(y*y*(n-1));
		sum1+=x,sum2+=y;
	}
	void init2(int xx,int yy)
	{
		ans2+=2*x*sum1+2*y*sum2,sum1-=xx,sum2-=yy;
	}
};
node a[100010];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y,a[i].init1();
	sum1-=a[1].x,sum2-=a[1].y;
	for(int i=1;i<n;i++) a[i].init2(a[i+1].x,a[i+1].y);
	cout<<ans1-ans2;
	return 0;
}