cho.sh
Notes
Loading...

Right Triangles

Time limit

5s

Memory limit

256 MB

Problem

You are given N distinct points on a two-dimensional plane. Among all ways to choose three distinct points and form a triangle, count how many of those triangles are right triangles.

Input

The first line contains the number of points, N. (3 <= N <= 1,500)

Each of the next N lines contains the x-coordinate and y-coordinate of one point, separated by a space. Every coordinate is an integer whose absolute value is at most 1,000,000,000, and no two given points have the same coordinates.

Output

Print the number of right triangles that can be formed from the given points.