Thanks to Jayun for technical support
Original question formula:
∑
i
=
1
n
∑
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 + (y_i-y_j)^2)}
i=1∑n?j=i + 1∑n?((xixj?)2 + (yiyj?)2)
Just consider first
x
x
x.
∑
i
=
1
n
∑
j
=
i
+
1
n
(
x
i
?
x
j
)
2
\sum_{i=1}^{n}\sum_{j=i + 1}^{n}{(x_i-x_j)^2}
i=1∑n?j=i + 1∑n?(xixj?)2
Simplification:
∑
i
=
1
n
∑
j
=
i
+
1
n
(
x
i
?
x
j
)
2
=
∑
i
=
1
n
∑
j
=
i
+
1
n
(
x
i
2
+
x
j
2
?
2
x
i
x
j
)
=
∑
i
=
1
n
(
(
n
?
i
)
x
i
2
+
∑
j
=
i
+
1
n
(
x
j
2
?
2
x
i
x
j
)
)
=
∑
i
=
1
n
(
(
n
?
i
)
x
i
2
+
(
i
?
1
)
[
1
]
x
i
2
?
2
∑
j
=
i
+
1
n
x
i
x
j
)
=
∑
i
=
1
n
(
(
n
?
1
)
x
i
2
?
2
x
i
∑
j
=
i
+
1
n
x
j
)
\begin{align} & amp;\quad~ \sum_{i=1}^{n}\sum_{j=i + 1}^{n}{(x_i-x_j)^2}\ & amp;= \sum_{i=1}^{n}\sum_{j=i + 1}^{n}{(x_i^2 + x_j^2-2x_ix_j)}\ & amp;=\sum_{i=1} ^{n}{\left((n-i)x_i^2 + \sum_{j=i + 1}^{n}{(x_j^2-2x_ix_j)}\right)}\ & amp;=\sum_{ i=1}^{n}{\left((n-i)x_i^2 + (i-1)^{\color{Red}{\tiny [1]}}x_i^2-2\sum_{j=i + 1}^{n}{x_ix_j}\right)}\ & amp;=\sum_{i=1}^{n}{\left((n-1)x_i^2-2x_i\sum_{j= i + 1}^{n}{x_j}\right)}\ \end{align}
? i=1∑n?j=i + 1∑n?(xixj?)2=i=1∑n?j=i + 1∑n?(xi2? + xj22xi?xj?) =i=1∑n?((n?i)xi2? + j=i + 1∑n?(xj22xi?xj?))=i=1∑n?((n?i)xi2? + (i?1)[1]xi22j=i + 1∑n?xi?xj?)=i=1∑n?((n?1)xi22xi?j=i + 1∑n? xj?)
(
4
)
[
1
]
:
i
<
j
(4){\color{Red}[1]} : i Just use the prefix sum to process the next sigma, that is ∑ i = 1 n ( ( n ? 1 ) x i 2 ? 2 x i ( s u m x n ? s u m x i ) ) \sum_{i=1}^{n}{\left((n-1)x_i^2-2x_i(sum_{x_n}-sum_{x_i})\right)} i=1∑n?((n?1)xi22xi?(sumxn?sumxi)) y y y Similarly, complexity O ( n ) O(n) O(n).
Open __int128, with reading and writing.
#include<bits/stdc + + .h>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
ll n;
__int128 x[100002],y[100002],h[100002],ns,ans;
inlinellrd()
{<!-- -->
ll rt=0;int fs=1;char c=getchar();
while(c<'0'||c>'9') {<!-- -->if(c=='-') fs=-1;c=getchar();}
while('0'<=c & amp; & amp;c<='9') {<!-- -->rt=rt*10-48 + c;c=getchar();}
return rt*fs;
}
void print(__int128 pt)
{<!-- -->
if(pt<0)
{<!-- -->
putchar('-');
pt=-pt;
}
if(pt>9) print(pt/10);
putchar(char(pt + 48));
}
int main()
{<!-- -->
// freopen("dis.in","r",stdin);
// freopen("dis.out","w",stdout);
n=rd();
for(int i=1;i<=n; + + i)
{<!-- -->
x[i]=rd(),y[i]=rd();
h[i]=x[i] + h[i-1];
}
ns=h[n];
for(int i=1;i<=n; + + i)
ans + =(n-1)*x[i]*x[i]-2*x[i]*(ns-h[i]);
for(int i=1;i<=n; + + i)
h[i]=y[i] + h[i-1];
ns=h[n];
for(int i=1;i<=n; + + i)
ans + =(n-1)*y[i]*y[i]-2*y[i]*(ns-h[i]);
print(ans);
return 0; //freopen?
}
/*
*/
//-static-libgcc -std=c + + 14 -Wall -Wl,--stack=134217728