Number of Right Triangles

Time limit1sMemory limit128 MB

Summary

Given up to 1500 planar points, count triples forming a right triangle, requiring an approach faster than brute force O(N^3).

Level: Hard8 of 10
Topics: Math, Geometry, Sorting
Solved: No attempts yet

Problem

There are N distinct points on a two-dimensional plane.

Choose three distinct points. Count how many choices form a triangle with one 90-degree angle. The same set of three points is counted only once.

Input

The first line contains the number of points N. (3 <= N <= 1500)

Each of the next N lines contains the x-coordinate and y-coordinate of one point, separated by a space. Every coordinate is between -10^9 and 10^9, inclusive.

No two points have the same coordinates.

Output

Print the number of right triangles on the first line.

Examples3

Example 1
Input
```
3
4 2
2 1
1 3
```
Expected output
```
1
```
Example 2
Input
```
4
5 0
2 6
8 6
5 7
```
Expected output
```
0
```
Example 3
Input
```
5
-1 1
-1 0
0 0
1 0
1 1
```
Expected output
```
7
```