# Antipodal Points Codechef Solution | APRIL CHALLENGE

Share:

Antipodal Points Codechef Solution

You are given a set of NN distinct points P1,P2,P3,…,PNP1,P2,P3,…,PN on a 22-D plane.

A triplet (i,j,k)(i,j,k) is called a holy triplet if

• 1≤i<j<k≤N1≤i<j<k≤N
• PiPi, PjPj and PkPk are non-collinear and
• Any two of the points PiPi, PjPj and PkPk are antipodal points of the circle that passes through all three of them.

Two points on a circle are said to be antipodal points of the circle if they are diametrically opposite to each other.

Find the total number of holy triplets.

### Input Format

• The first line contains a single integer TT – the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer NN – the number of points.
• Each of the next NN lines contains two space separated integers xixi and yiyi, denoting the co-ordinates of ii-th point PiPi.

### Output Format

For each test case output a single line denoting the number of holy triplets.

### Constraints

• 1≤T≤101≤T≤10
• 3≤N≤20003≤N≤2000
• Sum of NN over all test cases does not exceed 20002000
• −109≤xi,yi≤109−109≤xi,yi≤109
• All points P1,P2,…,PNP1,P2,…,PN in each test case are distinct.

### Sample Input 1

``````1
4
0 1
0 -1
1 0
-1 0
``````

### Sample Output 1

``````4
``````

### Explanation

Test case 1: The holy triplets in this case areHoly Triplet(1,2,3)(1,2,4)(1,3,4)(2,3,4)1≤i<j<k≤N✓✓✓✓Non collinear✓✓✓✓Antipodal points1 and 21 and 23 and 43 and 4