Squared Distances
National Olympiad — Municipal round (2022 season)
Submission name: points.cpp
Problem summary
Find the sum of squared Euclidean distances over all unordered pairs of N points.
Input
N, then N coordinate pairs X Y.
Output
The sum of squared pair distances, as an integer.
Constraints
1 ≤ N ≤ 100000; −10000 ≤ X,Y ≤ 10000.
Worked example
An independently prepared example for this explanation.
Input
4 1 1 -1 -1 1 -1 -1 1
Output
32
Solution analysis
- Expand one squared coordinate difference: (x[i]−x[j])² = x[i]²+x[j]²−2*x[i]*x[j]. The same formula applies independently to y.
- Summing over all unordered pairs gives N*sum(x²)−sum(x)² for the x contribution, and the analogous y contribution. Accumulate only the two coordinate sums and the sum of x²+y², then evaluate this expression.
- For the four sample corners, both coordinate sums are zero and the total sum of x²+y² is eight. The result is 4*8−0−0=32. For a single point, both terms cancel to zero.
Why it works
In N*sum(x²)−sum(x)², the diagonal square terms cancel once, leaving each x[i]² exactly N−1 times and each pair product −2*x[i]*x[j]. These are exactly the expansion of the sum of all unordered squared differences. Applying the same identity to y proves the distance result.
Watch out. Use signed 64-bit arithmetic before multiplication; all intermediate magnitudes fit within 64 bits under the bounds. Do not take square roots or count ordered pairs twice.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
// Algorithm: Expand one squared coordinate difference: (x[i]−x[j])² = x[i]²+x[j]²−2*x[i]*x[j].
using namespace std;
int main(){
int n;
cin>>n;
long long sumX=0,sumY=0,sumSquares=0;
for(int i=0;i<n;++i){
long long x,y;
cin>>x>>y;
sumX+=x;
sumY+=y;
sumSquares+=x*x+y*y;
}
cout<<n*sumSquares-sumX*sumX-sumY*sumY<<'\n';
}