TRICHEF - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Utkarsh Saxena
Testers: Misha Chorniy
Editorialist: Praveen Dhinwa

DIFFICULTY:

medium

PREREQUISITES:

prefix sums, data structures

PROBLEM:

You are given n distinct points in 2-D 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 non-zero 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

| \, \frac{1}{2} *\, ((x_1 y_2 - x_2 y_1) + (x_2 y_3 - x_3 y_2) + (x_3 y_1 - x_1 y_3)) \, |
= | \, \frac{1}{2} *\, ((x_1 y_2 + x_2 y_3 + x_3 y_1 ) - (y_1 x_2 + y_2 x_3 + y_3 x_1 )) \, |

Now there can be two cases.

Case 1: Two vertices of the triangle have the same x-coordinate.
Wlog assume the vertices 1 and 2 have same x coordinates, i.e. x_1 = x_2.

Area reduces to

| \, \frac{1}{2} *\, ((x_1 y_2 - x_1 y_1) + (x_1 y_3 - x_3 y_2) + (x_3 y_1 - x_1 y_3)) \, |
= | \, \frac{1}{2} *\, (x_1 (y_2 - y_1) - x_3 (y_2 - y_1)) \, |
= |\, \frac{1}{2} (x_1 - x_3) (y_2 - y_1) \, |

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

= \frac{1}{2} \, |y_2 - y_1| * |\, (x_1 - x_3) \, |

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 x-coordinate.

Wlog assume x_1 = 0, x_2 = 1 and x_3 = 3.

The formula for the area reduces to

|\, \frac{1}{2} (y_1 + y_3 - 2 y_2) \, |

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 pre-computing 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.

Setters and Tester Solution Codes

Setter’s solution
Tester’s solution

1 Like
2

Thanks for this @admin Great Slides and the tutorials are also quite good :slight_smile:

3

Can anyone help facing problem to convert the above approach into code specially the case 2. Thanks in advance :slight_smile: @vijju123

4

X can be only 1,2,3 not 0,1,2.

5

@admin Isn’t the complexity of setter’s solution is O(n^3) because innermost while loop can have O(n) complexity in the worst case(Though I understand the input is small but just making sure for the general case).

	for(int i = 0; i < a[0].size(); i++) {
		int start = 0;
		for(int j = 0; j < a[2].size(); j++) {
			ll tot = a[0][i] + a[2][j];
			while(start < cnt[1] && 2*a[1][start] < tot) start++;
			ll contri = ((tot * start) - (2LL * pre[start])) + ((2LL * (pre[cnt[1]] - pre[start])) - (tot * (cnt[1] - start)));
			ans += contri;
		}
	}

It can be improved to O(n^2(log n)) by using simple binary search.