All-Ukrainian School Olympiad in Informatics E: Points

問題概要

２次元平面上にN(<10^5)個の点が与えられる。各2点間の距離の2乗の総和を求める問題。

解法

まず、線形性からX成分とY成分は完全に分離して考えてよいことが分かる。
S:=Σ{x[i]^2}, K:=Σ{x[i]}とすると、各jに対して、Σ_i{(x[j]-x[i])^2}=Σ_i{x[j]^2 + x[i]^2 - 2*x[j]*x[i]} = Σ_i{x[i]^2} + N*x[j]^2 - 2*x[j]*Σ_i{x[i]} = S + N*x[j]^2 - 2*x[j]*Kなので、前処理でS,Kを計算しておけば定数時間でΣ_i{(x[j]-x[i])^2}を求められる。あとはこれを各jについて足し合わせて重複分２で割ればお終い。

感想

オーバーフローと、点が重なったときの処理を間違えてWA連発した。

#include <cstdio>
#include <vector>
#include <iostream>
#include <set>
using namespace std;

typedef long long ulong;
int N;

inline long long sq(int x){ return (long long)x*x; }

ulong solve(vector<int>& vs){
	ulong ret = 0;
	ulong S = 0, K = 0;
	for(int i=0; i<N; i++){
		S += sq(vs[0] - vs[i]);
		K += vs[0] - vs[i];
	}

	for(int i=0; i<N; i++){
		ret += S + (ulong)N*sq(vs[i] - vs[0]) + 2*(long long)(vs[i] - vs[0])*K;
	}

	return ret/2;
}

int main(){
	vector<int> xs, ys;
	scanf("%d",&N);
	set<pair<int,int> > ss;
	for(int i=0; i<N; i++){
		int x, y;
		scanf("%d%d",&x,&y);
		//if(ss.insert( make_pair(x,y)).second){
			xs.push_back(x);
			ys.push_back(y);
		//}
	}
	N = xs.size();
	ulong ans = solve(xs) + solve(ys);
	cout << ans << endl;
	return 0;
}