COCI 2007/2008, Contest #3

Task 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 ≤ N ≤ 100 000), the number of points.

Each of the following N lines contains two integers X and Y (1 ≤ X, Y ≤ 100 000), the coordinates of one point.

No pair of points will share the same pair of coordinates.

Output

Output the number of triangles.

Scoring

In 40% of all test cases, N will be less than 100.

In 70% of all test cases, N will be less than 10 000.

Examples

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

All Submissions
Best Solutions

Point Value: 7 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 30, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)