Triangles — Kattis Problem

Revision en2, by I_love_a0666, 2017-03-25 23:38:22

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?

Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English I_love_a0666 2017-03-25 23:38:22 339 Tiny change: 'a(i, j, k)$\n\nThank' -> 'a(i, j, k)^2$\n\nThank'
en1 English I_love_a0666 2017-03-25 23:14:00 282 Initial revision (published)