Problem Description

Given $n$ points on a plane, compute how many different right triangles there are such that all their vertices are among the given points, and both legs are parallel to the coordinate axes.

Two right triangles are different if and only if they have at least one different vertex.

Input Format

The first line contains an integer $n$, the number of points.

The next $n$ lines each contain two integers, giving the coordinates of a point.

Output Format

Output the number of right triangles.

3
4 2
2 1
1 3

0

5
1 2
2 1
2 2
2 3
3 2

4

6
10 10
20 10
10 20
20 20
30 20
30 30

8

Hint

Constraints

• For $40\%$ of the testdata, it is guaranteed that $n<100$.
• For $70\%$ of the testdata, it is guaranteed that $n<10^4$.
• For $100\%$ of the testdata, it is guaranteed that $3\le n\le 10^5$, the coordinate values are between $1$ and $10^5$, and no two points have the same coordinates.

Notes

This problem is translated from COCI2007-2008 CONTEST #3 T4 DEJAVU.

Translated by ChatGPT 5