Problem E
Dejavu
$N$ points are placed in the coordinate plane.
Write a program that calculates how many ways we can choose three points so that they form a right triangle with legs parallel to the coordinate axes.
A right triangle has one 90-degree internal angle. The legs of a right triangle are its two shorter sides.
Input
The first line of input contains the integer $N$ ($3 \le N \le 100\, 000$), the number of points.
Each of the following $N$ lines contains two integers $X$ and $Y$ ($1 \le X, Y \le 100\, 000$), the coordinates of one point.
No pair of points will share the same pair of coordinates.
Output
Output the number of triangles.
Sample Input 1 | Sample Output 1 |
---|---|
3 4 2 2 1 1 3 |
0 |
Sample Input 2 | Sample Output 2 |
---|---|
5 1 2 2 1 2 2 2 3 3 2 |
4 |
Sample Input 3 | Sample Output 3 |
---|---|
6 10 10 20 10 10 20 20 20 30 20 30 30 |
8 |