Given N points in a plane, find the number of acute triangles formed using these points as vertices.
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
Given a point O, all (X, Y)'s such that 90o ≤ ∠XOY ≤ 270o can be found in O(N log N) time. Using this, we can find the total number of non-acute angles in O(N2 log N) time by setting all points in the set as O one by one.
Here is how to find the number of pairs (X, Y) such that 90o ≤ ∠XOY ≤ 270o:
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 ith point in sorted order. Set X=P, then points Y for which ∠XOY is non acute are precisely those for which the anti-clockwise ∠ XOY lies between 900 and 270o. 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, u and v can be found by brute force in O(N) time. Now as X goes anticlockwise (X=P, P 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.
Can be found here
Can be found here