[BOJ 25952] Rectangles

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 1G

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

An axis-parallel rectangle is a rectangle with sides parallel to the $x$-axis or the $y$-axis. Also its four vertices are different from each other.</p>

For a set $S$ of points in the plane, an axis-parallel rectangle is called to be contained in $S$ if it has, as its vertices, four points belonging to $S$.

For example, in the left of Figure J.1, a set $S$ of ten points is given in the plane. Then as the right of Figure J.1, there are three axis-parallel rectangles contained in $S$.

Figure J.1 There are three axis-parallel rectangles contained in the given set of points.

Given a set $S$ of $n$ distinct points in the plane, write a program to output the number of all the axis-parallel rectangles contained in $S$.

입력 형식

Your program is to read from standard input. The input starts with a line containing an integer $n$ ($1 ≤ n ≤ 70\,000$), where $n$ is the number of points given in the plane. In the following $n$ lines, each line contains two integers that represent, respectively, the $x$-coordinate and the $y$-coordinate of a point. These coordinate values are between $0$ and $10^5$ and all the given points are distinct.

출력 형식

Your program is to write to standard output. Print exactly one line. The line should contain the number of axis-parallel rectangles contained in the given point set.

예제 입력 1

4
0 0
0 1
1 0
1 1

예제 출력 1

1

예제 입력 2

4
0 0
0 1
1 0
1 2

예제 출력 2

0

예제 입력 3

10
1 1
3 1
6 1
3 3
6 3
8 3
1 4
6 4
3 6
8 6

예제 출력 3

3

Comments

There are no comments at the moment.