题面

给定 $n$ 个点 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ ，求出 $\sum_{i=1}^{n}\sum_{j=i+1}^{n}{((x_i-x_j)^2+(y_i-y_j)^2)}$ 。

$2\le n \le 10^5,|x| \le 10^5,|y| \le 10^5$ 。

题解

简单题。对于 $x$ ，式子变成 $\sum_{i=1}^n\left((i-1)x_i^2+(n-i)x_i^2-2(\text{sum~x}_n-\text{sum~x}_i)x_i\right)$ ，其中 $\text{sum~x}$ 表示前缀和。 $y$ 同理。 $\mathcal{O}(n)$ 。

要开 __int128。

代码

const int N = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

void Print (__int128 x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) Print(x / 10);
	putchar((x % 10) + '0');
}

namespace Main {
	int n;
	__int128 x[N], sx[N], x2[N];
	__int128 y[N], sy[N], y2[N];
	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) {
			x[i] = Read(), y[i] = Read();
			sx[i] = sx[i - 1] + x[i];
			x2[i] = x[i] * x[i];
			sy[i] = sy[i - 1] + y[i];
			y2[i] = y[i] * y[i];
		}
		__int128 ans = 0;
		for (int i = 1; i <= n; i++) {
			ans += x2[i] * (n - i);
			ans -= x[i] * (sx[n] - sx[i]) * 2;
			ans += x2[i] * (i - 1);
			ans += y2[i] * (n - i);
			ans -= y[i] * (sy[n] - sy[i]) * 2;
			ans += y2[i] * (i - 1);
		}
		Print(ans); putchar(10);
		return 0;
	}
}

int main () {
	freopen("dis.in", "r", stdin);
	freopen("dis.out", "w", stdout);
	Main::main();
	return 0;
}