아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Rectangles

시간 제한2초메모리 제한1024 MB

요약
서로 다른 n개의 점이 주어질 때, 네 꼭짓점이 모두 주어진 점인 축에 평행한 직사각형의 개수를 센다. 개수가 클 수 있어 단순한 쌍 조합 열거로는 부족하다.
난이도

보통10점 중 7점

유형
기하, 해시맵, 정렬, 조합론
정답자
아직 제출이 없습니다

문제

An axis-parallel rectangle is a rectangle with sides parallel to the xx-axis or the yy-axis. Also its four vertices are different from each other.

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

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

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

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

입력

Your program is to read from standard input. The input starts with a line containing an integer nn (1≤n≤70,0001 ≤ n ≤ 70\\,000), where nn is the number of points given in the plane. In the following nn lines, each line contains two integers that represent, respectively, the xx-coordinate and the yy-coordinate of a point. These coordinate values are between 00 and 10510^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.

예제3

  1. 예제 1

    입력
    4
    0 0
    0 1
    1 0
    1 1
    
    예상 출력
    1
    
  2. 예제 2

    입력
    4
    0 0
    0 1
    1 0
    1 2
    
    예상 출력
    0
    
  3. 예제 3

    입력
    10
    1 1
    3 1
    6 1
    3 3
    6 3
    8 3
    1 4
    6 4
    3 6
    8 6
    
    예상 출력
    3