Golden Triangles

Bessie, while on guard duty, entertains herself by counting golden triangles made by cows placed on a 2D grid. Each cow is given by its coordinates \( (X_i, Y_i) \) for \(1 \le i \le N\). A triangle is considered golden if it wholly contains the origin \( (0,0) \). It is guaranteed that the origin does not lie on any line through two cows, and no cow is located at the origin.

If you form all possible triangles from the set of cow coordinates, determine how many of these triangles are golden.

Hint: A triangle contains the origin if and only if its vertices are not confined within any half-plane (i.e. not all contained within an arc of \( \pi \) radians). Using this observation, one can sort the points by angle and then use a two-pointer technique to count the number of triangles that do not contain the origin. Finally, subtract this count from \( \binom{N}{3} \) to obtain the answer.

inputFormat

The first line contains an integer \( N \) (\( 1 \le N \le 100,000\)), representing the number of cows.

Each of the following \( N \) lines contains two space-separated integers \( X_i \) and \( Y_i \) (\( -100,000 \le X_i, Y_i \le 100,000 \)), indicating the coordinates of the \( i \)-th cow.

outputFormat

Output a single integer, the number of golden triangles that contain the origin.

sample

5
-5 0
0 2
11 2
-11 -6
11 -5

5