PROBLEM LINK:
Author: Utkarsh Saxena
Testers: Misha Chorniy
Editorialist: Praveen Dhinwa
DIFFICULTY:
medium
PREREQUISITES:
prefix sums, data structures
PROBLEM:
You are given n distinct points in 2D plane. Their x coordinates can be either 0, 1 or 2.
Find the sum of areas of the triangles made by all the \binom{n}{3} triplets of points. The value of n is around 10^3.
SOLUTION
Note that the x coordinates are only 0, 1 or 2. Suppose the three points have same x, then the area will be zero. So, the triangles with nonzero areas should be made of points which have at least two points with different x coordinates.
The formula for finding area of triangle with coordinates of points (x1, y1), (x2, y2), (x3, y3) will be
Now there can be two cases.
Case 1: Two vertices of the triangle have the same xcoordinate.
Wlog assume the vertices 1 and 2 have same x coordinates, i.e. x_1 = x_2.
Area reduces to
Note that the coordinate y_3 doesnâ€™t matter for the area.
We can pick all possible pairs of (x_1, y_1) and (x_1, y_2). Note that value of y_2  y_1 will be fixed after this.
Area formula becomes
The term \frac{1}{2} \, y_2  y_1 can be taken common out of this formula. Remaining term just becomes sum of values of x_1  x_3. We can find this by finding sum of x coordinates of points with their x coordinates < x_1 and sum of x coordinates of points with their x coordinates > x. Both of these can be computed by maintaining using prefix sums over x coordinates of the points.
This takes \mathcal{O}(N^2) time.
Case 2: All the three vertices of the triangle have different xcoordinate.
Wlog assume x_1 = 0, x_2 = 1 and x_3 = 3.
The formula for the area reduces to
We can the absolute sign by considering the two cases.

y_1 + y_3 \geq 2 y_2:
Fix y_1 and y_3 and find the sum of all valid y_2 satisfying this inequality. This can be done efficiently by precomputing partial sums.  y_1 + y_3 < 2 y_2: This case can also be dealt similar to the case above.
The overall complexity of this program will be \mathcal{O}(n^2).
Reference slides describing this approach be found here.