테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 직각 삼각형 ======

===== 풀이 =====
  * {{myicon>p4}} [[ps:problems:boj:3008]] 와 비슷해보이지만, 축에 평행한 직각삼각형만 세면 된다는 조건이 들어가기 때문에 훨씬 간단하다.
  * 한 점을 고정했을때, 그 점과 x값이 같은 점 한개와 y값이 같은 점 한개를 찾으면 그 점을 직각인 꼭짓점으로 갖는 직각삼각형을 찾을 수 있다.
  * 결국, 점 P를 직각인 꼭짓점으로 갖는 직각삼각형의 개수는, {P와 x좌표가 같은 점의 개수} * {P와 y좌표가 같은 점의 개수}로 계산할수 있다. x좌표 값마다 점의 개수를 세어놓은 딕셔너리와, y좌표 값마다 점의 개수를 세어놓은 딕셔너리를 미리 O(N)에 만들어 놓는다면, 특정 점을 직각인 꼭짓점으로 갖는 직각삼각형의 개수를 O(1)에 계산 가능하다. 이것을 N개의 점에 대해서 모두 구하면 O(N)이 걸린다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 3000. 직각 삼각형".

- Problem link: https://www.acmicpc.net/problem/3000
- Solution link: http://www.teferi.net/ps/problems/boj/3000

Tags: [geometry]
"""

import collections
import sys


def main():
    N = int(sys.stdin.readline())
    X_and_Y = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    x_counter = collections.Counter(x for x, y in X_and_Y)
    y_counter = collections.Counter(y for x, y in X_and_Y)
    answer = sum(
        (x_counter[x_i] - 1) * (y_counter[y_i] - 1) for x_i, y_i in X_and_Y
    )

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>


{{tag>BOJ ps:problems:boj:실버_1}}