### I_love_a0666's blog

By I_love_a0666, history, 3 years ago, , Hello,

I was trying out this problem on Kattis, but I couldn't come up with an efficient solution. It seems like an interesting problem. Here is what the problem basically amounts to:-

Given N (N ≤ 1000000) points on a 2D Plane (0 ≤ xi, yi ≤ 1000000), compute . Here, area(i, j, k) denotes the area of the triangle formed by points i, j, k.

Can someone provide hints? Comments (8)
 » 3 years ago, # | ← Rev. 3 →   Sorry this was for when the sum was over area(i,j,k). I didn't see that it was squared. I'm sorry.
•  » » Thank you for your response. Yes, I figured out how to solve it for that as well. I couldn't quite extend it to sums of squares though and was wondering if there's a nicer solution altogether.
 » There is very messy way to do it. You can take each term and express it terms of coordinates of i, j, k. Then group up terms so that computation would be O(N).
•  » » Could you elaborate some more on your approach?
• »
»
»
6 weeks ago, # ^ |
Rev. 5

Sorry for the late post, but this method is perfectly feasible and gets AC. THe steps are extremely messy, but the result is beautiful.

First, express the answer like so:

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N\frac{(y_i(x_j-x_k)+y_j(x_k-x_i)+y_k(x_i-x_j))^2}{24}$

[Extremely long expansion redacted]

Then, sum by parts, and reduce the nested sum into products of one-layer sums for each of the 21 summands:

$A=\sum_{i=1}^Nx_i$
$B=\sum_{i=1}^Nx_iy_i$
$C=\sum_{i=1}^Ny_i$
$D=\sum_{i=1}^Nx_i^2$
$E=\sum_{i=1}^Ny_i^2$

# 1

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_i^2y_j^2$
$NDE$

# 2

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_i^2y_jy_k$
$-2DC^2$

# 3

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_i^2y_k^2$
$NDE$

# 4

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_ix_jy_iy_j$
$-2NB^2$

# 5

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_ix_jy_iy_k$
$2ABC$

# 6

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_ix_jy_jy_k$
$2ABC$

# 7

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_ix_jy_k^2$
$-2EA^2$

# 8

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_ix_ky_iy_j$
$2ABC$

# 9

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_ix_ky_iy_k$
$-2NB^2$

# 10

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_ix_ky_j^2$
$-2EA^2$

# 11

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_ix_ky_jy_k$
$2ABC$

# 12

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_j^2y_i^2$
$NED$

# 13

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_j^2y_iy_k$
$-2DC^2$

# 14

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_j^2y_k^2$
$NDE$

# 15

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_jx_ky_i^2$
$-2EA^2$

# 16

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_jx_ky_iy_j$
$2ABC$

# 17

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_jx_ky_iy_k$
$2ABC$

# 18

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_jx_ky_jy_k$
$-2NB^2$

# 19

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_k^2y_i^2$
$NED$

# 20

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_k^2y_iy_j$
$-2DC^2$

# 21

$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_k^2y_j^2$
$NED$

The result is

$6(2ABC+NDE-DC^2-NB^2-EA^2)$

, and dividing by 24 gives

$\frac{2ABC+NDE-DC^2-NB^2-EA^2}{4}$

.

You need to use Python, though (intermediate steps go past the range of a 128-bit integer)

[Edit because math equation broke the page] [Edit 2: Latex Gods are not happy]