만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

감시자

면접 대비

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

요약
맨해튼 거리와 유클리드 거리가 같은 점 쌍의 개수를 구합니다.
난이도

쉬움10점 중 3점

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

문제

감시자들이 위험에 처해 있어서 Doctor Manhattan과 그의 친구 Daniel Dreiberg가 가능한 한 빨리 그들에게 경고해야 한다. 평면 위에 nn명의 감시자가 있고, ii번째 감시자는 점 (xi,yi)(x_i, y_i)에 있다.

Doctor Manhattan은 감시자 ii와 jj 사이의 거리를 ∣xi−xj∣+∣yi−yj∣|x_i - x_j| + |y_i - y_j|로 계산한다. 평범한 사람인 Daniel은 같은 거리를 (xi−xj)2+(yi−yj)2\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}로 계산한다.

작전의 성공은 두 방식으로 계산한 거리가 같은 쌍 (i,j)(i, j) (1≤i<j≤n1 \leq i < j \leq n)의 개수에 달려 있다. 이 쌍의 개수를 구하라.

입력

첫 줄에 정수 nn (1≤n≤200 0001 \leq n \leq 200\,000)이 주어진다. 감시자의 수이다.

이어지는 nn개의 줄에는 정수 xix_i와 yiy_i (∣xi∣,∣yi∣≤109|x_i|, |y_i| \leq 10^9)가 주어진다.

출력

맨해튼 거리와 유클리드 거리가 같은 감시자 쌍의 개수를 출력한다.

힌트

첫 번째 예제에서 감시자 1과 2 사이의 거리는 Doctor Manhattan 방식으로 ∣1−7∣+∣1−5∣=10|1 - 7| + |1 - 5| = 10이고, Daniel 방식으로 (1−7)2+(1−5)2=2⋅13\sqrt{(1 - 7)^2 + (1 - 5)^2} = 2 \cdot \sqrt{13}이다. 쌍 (1,1)(1, 1), (1,5)(1, 5), (7,5)(7, 5), (1,5)(1, 5)에서는 두 방식이 같은 거리를 계산한다.

예제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