BOJ 1711: 직각삼각형 (python)

https://www.acmicpc.net/problem/1711

직각삼각형 판단법
두 선분의 기울기가 (x,y) (-y,x) 일때 직각삼각형을 이룬다. (아래 참조)

• 피타고라스 방식은 3중 for문 이므로 시간적으로 비효율

defaultdict 및 math.gcd(최대공약수)를 활용

from math import gcd
from collections import defaultdict

n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
answer = 0

for i in range(n):
    check = defaultdict(int)
    for j in range(n):
        if i == j:
            continue
		
        x, y = lst[i][0] - lst[j][0], lst[i][1] - lst[j][1]		
        // 최대공약수를 통해 기울기를 설정
        val = gcd(x, y)
        x, y = x // val, y // val
        // 각 점 마다 다른 점과의 기울기를 defaultdict에 저장 
        check[(x, y)] += 1
	
    // defaultdict를 순회하면서 (-y,x)와 매칭되는 값과 곱셈 후 추가
    for nx, ny in check:
        if check.get((-ny, nx)):
            answer += check[(nx, ny)] * check[(-ny, nx)]

print(answer)