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

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

Watchmen

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

요약
두 점의 맨해튼 거리와 유클리드 거리가 같아지는 점 쌍의 개수를 센다.
난이도

보통10점 중 5점

유형
수학, 해시맵, 정렬
정답자
아직 제출이 없습니다

문제

Watchmen are in a danger and Doctor Manhattan together with his friend Daniel Dreiberg should warn them as soon as possible. There are nn watchmen on a plane, the ii-th watchman is located at point (x_i,y_i)(x\_i, y\_i).

They need to arrange a plan, but there are some difficulties on their way. As you know, Doctor Manhattan considers the distance between watchmen ii and jj to be ∣x_i−x_j∣+∣y_i−y_j∣|x\_i - x\_j| + |y\_i - y\_j|. Daniel, as an ordinary person, calculates the distance using the formula (x_i−x_j)2+(y_i−y_j)2\sqrt{(x\_i - x\_j)^2 + (y\_i - y\_j)^2}.

The success of the operation relies on the number of pairs (i,j)(i, j) (1≤i<j≤n1 \leq i < j \leq n), such that the distance between watchman ii and watchmen jj calculated by Doctor Manhattan is equal to the distance between them calculated by Daniel. You were asked to compute the number of such pairs.

입력

The first line of the input contains the single integer nn (1≤n≤200,0001 \leq n \leq 200\\,000) --- the number of watchmen.

Each of the following nn lines contains two integers x_ix\_i and y_iy\_i (∣x_i∣,∣y_i∣≤109|x\_i|, |y\_i| \leq 10^9).

출력

Print the number of pairs of watchmen such that the distance between them calculated by Doctor Manhattan is equal to the distance calculated by Daniel.

힌트

In the first sample, the distance between watchman 11 and watchman 22 is equal to ∣1−7∣+∣1−5∣=10|1 - 7| + |1 - 5| = 10 for Doctor Manhattan and (1−7)2+(1−5)2=2⋅13\sqrt{(1 - 7)^2 + (1 - 5)^2} = 2 \cdot \sqrt{13} for Daniel. For pairs (1,1)(1, 1), (1,5)(1, 5) and (7,5)(7, 5), (1,5)(1, 5) Doctor Manhattan and Daniel will calculate the same distances.

예제2

  1. 예제 1

    입력
    3
    1 1
    7 5
    1 5
    
    예상 출력
    2
    
  2. 예제 2

    입력
    6
    0 0
    0 1
    0 2
    -1 1
    0 1
    1 1
    
    예상 출력
    11