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.