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

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

친화적인 점

시간 제한1초메모리 제한128 MB

요약
x좌표와 y좌표가 각각 서로 다른 n개의 점 가운데 두 점을 마주보는 꼭짓점으로 하는 직사각형 안에 다른 점이 들어 있지 않은 쌍의 개수를 구합니다.
난이도

보통10점 중 7점

유형
세그먼트 트리, 정렬, 기하
정답자
아직 제출이 없습니다

문제

좌표평면 위에 nn개의 점이 있습니다. 모든 점의 xx좌표는 서로 다르고, yy좌표도 서로 다릅니다 (같은 xx좌표를 가진 두 점은 없고, 같은 yy좌표를 가진 두 점도 없습니다).

두 점을 마주 보는 두 꼭짓점으로 하고 각 변이 좌표축에 평행한 직사각형을 그렸을 때, 그 직사각형 내부에 다른 점이 하나도 들어 있지 않으면 두 점은 서로 친화적이라고 합니다. 친화적인 점의 쌍이 몇 개인지 세세요.

입력

첫째 줄에 점의 개수 nn (1≤n≤1051 \le n \le 10^5)이 주어집니다. 이어지는 nn개의 줄에는 각 점의 좌표 xx와 yy (0≤x,y≤1060 \le x, y \le 10^6)가 공백으로 구분되어 주어집니다.

출력

친화적인 점의 쌍의 개수를 정수 하나로 출력합니다.

예제1

  1. 예제 1

    입력
    4
    0 1
    1 2
    2 3
    3 0
    
    예상 출력
    5