Acute Triangles
Time limit4sMemory limit512 MB
Given n points, count the triangles with all three angles under 90 degrees. Total n across all test cases is at most 2000.
- Level
Medium7 of 10
- Topics
- Geometry, Two pointers, Sorting, Math
- Solved
- No attempts yet
Problem
Recently Moscow high school student Dmitri Zakharov set a new record for the number of points in d-dimensional space such that all triangles with vertices at those points are acute.
Tanya wants to compete with Dmitri. Of course, she plans to use a computer. To make a good start, she decided to solve the following problem. Given n points on a plane, find the number of acute triangles whose vertices are among those points. A triangle is acute if all of its angles are less than 90 degrees.
Input
The input data contains multiple test cases. The first line of input contains the integer t, the number of test cases (1 ≤ t ≤ 666).
Each test case is described by a line containing the integer n, the number of points (3 ≤ n ≤ 2000).
The following n lines contain two integers xi, yi each (-10^9 ≤ x, y ≤ 10^9), the coordinates of the points. In one test case all points are distinct.
The total number of points over all test cases of one input data does not exceed 2000.
Output
For each test case, output one line containing the number of acute triangles whose vertices are among the given points.