[Solution] Antipodal Points solution codechef

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

[Solution] Antipodal Points solution codechef

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

  • 1i<j<kN1≤i<j<k≤N
  • PiPiPjPj and PkPk are non-collinear and
  • Any two of the points PiPiPjPj 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.

[Solution] Antipodal Points solution codechef

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

Sample Input 1 

0 1
0 -1
1 0
-1 0

Sample Output 1 


Antipodal Points solution Explanation

Test case 1: The holy triplets in this case are

Holy Triplet(1,2,3)(1,2,4)(1,3,4)(2,3,4)1i<j<kNNon collinearAntipodal points1 and 21 and 23 and 43 and 4

For Solution

Click here

Leave a Comment