102183: [AtCoder]ABC218 D - Rectangles

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

问题描述

我们在二维平面上有N个不同的点，编号为1,2,...,N。点i(1≤i≤N)的坐标为(x_i,y_i)。

有多少个矩形的顶点在给定的点中，且边与x轴或y轴平行？

限制条件

• 4≤N≤2000
• 0≤x_i, y_i≤10^9
• (x_i,y_i)≠(x_j,y_j) (i≠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的矩形。

样例输入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