TAACUTE - Editorial

[utkarsh_lath]

Problem Link:

Practice

Contest

Difficulty:

Easy-Medium

Pre-requisites:

Ad Hoc

Problem:

Given N points in a plane, find the number of acute triangles formed using these points as vertices.

Explanation:

It is harder to find all acute triangles because there is a restriction on each angle. It would be much easier to find the number of non-acute triangles, because that is equal to the number of non-acute angles(no triangle can have two non-acute angles).

So we set out to find the number of non-acute angles, and our final answer would be:

number of acute triangles = total number of triangles - number of non acute angles

idea

Given a point O, all (X, Y)'s such that 90^o ≤ ∠XOY ≤ 270^o can be found in O(N log N) time. Using this, we can find the total number of non-acute angles in O(N² log N) time by setting all points in the set as O one by one.

Details

Here is how to find the number of pairs (X, Y) such that 90^o ≤ ∠XOY ≤ 270^o:

Set O as origin and sort and relabel all the points P around O by the ∠POX it makes with X-axis.

Let P[i] denote the i^th point in sorted order. Set X=P[0], then points Y for which ∠XOY is non acute are precisely those for which the anti-clockwise ∠ XOY lies between 90⁰ and 270^o. All such Y’s are a contiguous subarray of P, and the number of such Y’s is v-u+1, where

u = smallest index such that ∠ XO(P[u]) ≥ 90 ^o
v = largest index such that ∠ XO(P[v]) ≤ 270 ^o

For X = P[0], u and v can be found by brute force in O(N) time. Now as X goes anticlockwise (X=P[1], P[2] etc.), points P[u] and P[v] keep shifting anti-clockwise as well. Therefore, we could update u and v as X moves anticlockwise by linearly searching anticlockwise.

The time complexity is O(N log N) for sorting and O(N) for rest of the procedure because X iterates over N points in one rotation around O, and u and v complete at most two rotations around O.

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here

[mastmaulaa]

@utkarsh_lath O(N) for picking each X and then O(N*logN) for sorting and finding all obtuse angles(between u,v) === O(N^2 *log N)

But you don’t need to sort every time you change X as sort order don’t change. Finding u,v will still take O(N) time hence wouldn’t it be a O(N^2) algo? Also, as you’ve mentioned, u and v will keep shifting in anticlockwise direction as X moves in anticlockwise direction and total number of shifts u,v will take will be <= 2N. Hence, won’t the order be O(Nlog N)?

[utkarsh_lath]

For a fixed O(center), you do not need to sort everytime you shift X. For a fixed O, the time complexity is O(N log N) as clearly stated in the section labelled idea.

The overall complexity is O(N^2 log N) because O can potentially be any point in the set, so for each point in the set, we make it the center and repeat the above procedure which works for a fixed center O.