Stupendous Bowties

Given N distinct integer points, count unordered pairs of axis-aligned right triangles that share only the right-angle vertex.

Medium6GeometryCombinatoricsHash mapMathNo attempts yetTime limit2sMemory limit512 MB

Problem

There are NN distinct points on the plane. The ii-th point sits at integer coordinates (xi,yi)(x_i, y_i).

A Fantastic Right Triangle uses three of the given points as its vertices, has positive area, and has both of its legs parallel to the axes: one leg is parallel to the xx-axis and the other is parallel to the yy-axis. The vertex where the two legs meet, the one whose interior angle is right, is called the triangle's Spectacular Vertex.

A Stupendous Bowtie is an unordered pair of Fantastic Right Triangles that share the same Spectacular Vertex and touch only at that point. Treat each triangle as a closed region that includes its boundary and its interior, so the pair forms a bowtie only when the intersection of the two triangles is exactly that shared vertex.

Count the Stupendous Bowties that exist among the given points.

Input

The first line contains the number of points NN.

Each of the next NN lines contains two integers xix_i and yiy_i separated by a space.

Output

Print, on a single line, the number of Stupendous Bowties that exist among the given points.

Limits

  • 1N1000001 \le N \le 100\,000
  • 100000xi100000-100\,000 \le x_i \le 100\,000
  • 100000yi100000-100\,000 \le y_i \le 100\,000
  • The NN given points are pairwise distinct.
  • The answer can exceed the range of a 32-bit integer.