/ 
Time Limit: 4 sec / Memory Limit: 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