#P6355. Count Axis-Aligned Right Triangles

    ID: 19571 Type: Default 1000ms 256MiB

Count Axis-Aligned Right Triangles

Count Axis-Aligned Right Triangles

Given nn points in the plane, count the number of distinct right triangles whose vertices are among the given points and whose legs are parallel to the coordinate axes. A triangle is considered valid if one of its vertices at (x,y)(x,y) forms the right angle with one side vertical and the other horizontal. Two triangles are different if they differ in at least one vertex.

inputFormat

The first line contains an integer nn (3n1053 \leq n \leq 10^5) --- the number of points. Each of the next nn lines contains two space-separated integers xx and yy (109x,y109-10^9 \leq x,y \leq 10^9) representing the coordinates of a point.

outputFormat

Print a single integer representing the number of distinct right triangles whose legs are parallel to the coordinate axes.

sample

4
0 0
0 1
1 0
1 1
1

</p>