D - Rectangles 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 400

問題文

2 次元平面上に N 個の相異なる点があり、1,2,\ldots ,N の番号がついています。点 i\,(1 \leq i \leq N) の座標は (x_i,y_i) です。

これらの点のうち 4 つを頂点とし、全ての辺が x 軸または y 軸に平行であるような長方形はいくつありますか?

制約

  • 4 \leq N \leq 2000
  • 0 \leq x_i, y_i \leq 10^9
  • (x_i,y_i) \neq (x_j,y_j) (i \neq j)
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
x_1 y_1
x_2 y_2
 \vdots 
x_N y_N

出力

答えを出力せよ。


入力例 1

6
0 0
0 1
1 0
1 1
2 0
2 1

出力例 1

3

1 、点 2 、点 3 、点 4 を頂点とする長方形、

1 、点 2 、点 5 、点 6 を頂点とする長方形、

3 、点 4 、点 5 、点 6 を頂点とする長方形

の合計 3 つです。


入力例 2

4
0 1
1 2
2 3
3 4

出力例 2

0

入力例 3

7
0 1
1 0
2 0
2 1
2 2
3 0
3 2

出力例 3

1

Score : 400 points

Problem Statement

We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?

Constraints

  • 4 \leq N \leq 2000
  • 0 \leq x_i, y_i \leq 10^9
  • (x_i,y_i) \neq (x_j,y_j) (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
 \vdots 
x_N y_N

Output

Print the answer.


Sample Input 1

6
0 0
0 1
1 0
1 1
2 0
2 1

Sample Output 1

3

There are three such rectangles:

the rectangle whose vertices are Points 1, 2, 3, 4,

the rectangle whose vertices are Points 1, 2, 5, 6,

and the rectangle whose vertices are Points 3, 4, 5, 6.


Sample Input 2

4
0 1
1 2
2 3
3 4

Sample Output 2

0

Sample Input 3

7
0 1
1 0
2 0
2 1
2 2
3 0
3 2

Sample Output 3

1