CodeForces 76E Points

给出n个点,求任意两点间距离的平方和。

暴力显然超时,可以把公式写出来,化简一下,发现预处理一下后缀和就可以o(n)出解了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std; const int maxn=+;
struct Point
{
long long x,y;
}p[maxn];
int n;
long long sum[maxn];
long long a[maxn]; long long get(int x)
{
long long res=;
int tot=;
if(x==) for(int i=;i<=n;i++) a[i]=p[i].x;
else for(int i=;i<=n;i++) a[i]=p[i].y;
sum[n+]=; for(int i=n;i>=;i--) sum[i]=sum[i+]+a[i];
for(int i=;i<=n;i++) res=res+a[i]*a[i]*(n-);
for(int i=;i<=n-;i++) res=res-*a[i]*sum[i+];
return res;
} int main()
{
scanf("%d",&n);
long long ans=;
for(int i=;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y);
ans=ans+get();
ans=ans+get();
printf("%lld\n",ans);
return ;
}
上一篇:直接下载完整chrome浏览器的方法


下一篇:蜗牛慢慢爬 LeetCode 19. Remove Nth Node From End of List [Difficulty: Medium]