可以把题目转换成求：
\[\sum_{i = 1}^{n} \sum_{j = i + 1} ^{n} [(x_i - x_j)^2 + (y_i - y_j)^2] \]继续化简:
\[=\sum_{i = 1}^{n} \sum_{j = i + 1} ^{n} (x_i - x_j)^2 + \sum_{i = 1}^{n} \sum_{j = i + 1} ^{n} (y_i - y_j)^2 \]\[= \sum_{i = 1}^n \sum_{j = i + 1}^{n}(x_i^2-2x_ix_j+x_j^2)+\sum_{i = 1}^n \sum_{j = i + 1}^{n}(y_i^2-2y_iy_j+y_j^2) \]\[= \sum_{i=1}^n(x_i^2+y_i^2)+\sum_{i=1}^n \sum_{j=i+1}^n (x_j^2 + y_j^2)-2\sum_{i=1}^n\sum_{j=i+1}^n (x_ix_j + y_iy_j) \]\[= \sum_{i=1}^{n} (x_i^2 + y_i^2) + \sum_{i = 2}^n[(i -1)\times (x_i^2 + y_i^2) ] - \sum_{i=1}^{n}(x_i\sum_{j=i+1}^n x_j + y_i\sum_{j=i+1}^n y_j)。 \]每一项都可以 \(\mathcal{O}(n)\) 的处理出来，总时间复杂度是 \(\mathcal{O}(n)\)。
代码没写，明天再写。
标签：iy,ix,CF76E,sum,Points,mathcal From： https://www.cnblogs.com/tttttttle/p/16633855.html