Counting Quadruples of Points
Practice
4.5 (2 votes)
Combinatorics
Geometry
Math
Medium
Meet in the middle
Problem
31% Success 3233 Attempts 30 Points 4.5s Time Limit 1024MB Memory 1024 KB Max Code
There are \(n\) points in the plane, the \(i^{th}\) of which is labeled \(A_i\) and has coordinates \((x_i, y_i)\). How many ordered quadruples of pairwise-distinct indices \((p,q,r,s)\) are there such that \(A_p A_q + A_r A_s = A_q A_r + A_p A_s\)?
Input Format :
The first line of input contains a single integer \(n\).
The next \(n\) lines of input each contain two space-separated integers \(x_i\) and \(y_i\).
Output Format :
Print a single integer: the number of ordered quadruples satisfying the above condition.
Constraints :
\(4 \le n \le 250\)
\(0 \le x_i, y_i \le 16\)
Note :
\(A_i A_j\) is the euclidean distance between points \(A_i\) and \(A_j\).
Submissions
Please login to view your submissions
Similar Problems
Points:30
4 votes
Tags:
CombinatoricsMathMediumNumber Theory
Points:30
5 votes
Tags:
Modular arithmeticCombinatoricsNumber theoryPrime FactorizationBasics of CombinatoricsAlgorithmsModular exponentiationMath
Points:30
18 votes
Tags:
CombinatoricsMathMedium
Editorial