만드는 중입니다

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

멋진 나비넥타이

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

요약
서로 다른 정수 좌표 점 N개가 주어질 때, 직각 꼭짓점만 공유하는 축에 평행한 직각삼각형 쌍의 개수를 센다.
난이도

보통10점 중 6점

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

문제

2차원 평면에 서로 다른 점 NN개가 있다. ii번째 점의 좌표는 정수 (xi,yi)(x_i, y_i)이다.

환상의 직각삼각형은 주어진 점 중 세 개를 꼭짓점으로 삼고, 면적이 00보다 크며, 두 직각변이 각각 좌표축과 평행한 삼각형이다. 다시 말해 한 직각변은 xx축과 평행하고 다른 직각변은 yy축과 평행하다. 두 직각변이 만나는 꼭짓점, 즉 내각이 직각인 꼭짓점을 그 삼각형의 특별한 꼭짓점이라고 부른다.

멋진 나비넥타이는 특별한 꼭짓점이 같은 환상의 직각삼각형 두 개의 순서 없는 쌍이며, 두 삼각형은 그 꼭짓점에서만 맞닿는다. 삼각형은 경계와 내부를 모두 포함하는 닫힌 영역으로 본다. 따라서 두 삼각형의 공통부분이 특별한 꼭짓점 하나뿐일 때만 멋진 나비넥타이가 된다.

주어진 점으로 만들 수 있는 멋진 나비넥타이의 개수를 구하라.

입력

첫째 줄에 점의 개수 NN이 주어진다.

다음 NN개의 줄에는 각각 두 정수 xix_i와 yiy_i가 공백으로 구분되어 주어진다.

출력

주어진 점으로 만들 수 있는 멋진 나비넥타이의 개수를 한 줄에 출력한다.

제한

  • 1≤N≤100 0001 \le N \le 100\,000
  • −100 000≤xi≤100 000-100\,000 \le x_i \le 100\,000
  • −100 000≤yi≤100 000-100\,000 \le y_i \le 100\,000
  • 주어진 NN개의 점은 모두 서로 다르다.
  • 정답은 32비트 정수 범위를 넘을 수 있다.

예제4

  1. 예제 1

    입력
    12
    -3 6
    1 6
    -1 4
    -3 2
    1 2
    4 2
    -4 -3
    -3 -3
    1 -3
    -1 -4
    1 -4
    -3 -6
    
    예상 출력
    8
    
  2. 예제 2

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

    입력
    3
    0 0
    5 0
    0 7
    
    예상 출력
    0
    
  4. 예제 4

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