Counting Quadruples of Points

4.5

2 votes
Combinatorics, Geometry, Math, Medium, Meet in the middle
Problem

There are n points in the plane, the ith of which is labeled Ai and has coordinates (xi,yi). How many ordered quadruples of pairwise-distinct indices (p,q,r,s) are there such that ApAq+ArAs=AqAr+ApAs

Input Format :

The first line of input contains a single integer n.

The next n lines of input each contain two space-separated integers xi and yi.

Output Format :

Print a single integer: the number of ordered quadruples satisfying the above condition.

Constraints :

4n250

0xi,yi16

 

Note :

AiAj is the euclidean distance between points Ai and Aj.

 

Sample Input
4
3 0
0 4
7 3
4 7
Sample Output
8
Time Limit: 4.5
Memory Limit: 1024
Source Limit:
Explanation

The eight quadruples are:

  • (0,1,3,2)
  • (0,2,3,1)
  • (1,0,2,3)
  • (1,3,2,0)
  • (2,0,1,3)
  • (2,3,1,0)
  • (3,1,0,2)
  • (3,2,0,1)
Editor Image

?