# Problem Link:

# 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 ^{2} 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^{0} 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