#include <bits/stdc++.h> using namespace std; int DistanceSum(int n, int *x, int *y){ int minx=4294967295, miny=4294967295; for (int a=0; a<n; a++) { minx=min(minx, x[a]); miny=min(miny, y[a]); } for (int a=0; a<n; a++) { x[a]-=minx; y[a]-=miny; } sort(x, x+n); sort(y, y+n); long long int bx=0, by=0; for (int a=0; a<n; a++) { bx+=x[a]-x[0]; by+=y[a]-y[0]; } long long int ans=(bx+by)%1000000000; for (int a=1; a<n; a++) { bx-=(n-a)*(x[a]-x[a-1]); by-=(n-a)*(y[a]-y[a-1]); ans=(ans+bx+by)%1000000000; } return ans; }