ALGORITHM

직각삼각형

난이도

Gold 5

인증

문제

2차원 평면에 N개의 점이 주어져 있다. 이 중에서 세 점을 골랐을 때, 직각삼각형이 몇 개나 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,500)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 좌표값은 절댓값이 1,000,000,000을 넘지 않는 정수이며, 주어지는 모든 점의 좌표는 다르다.

출력

첫째 줄에 직각삼각형의 개수를 출력한다.

예제 입력 

5
-1 1
-1 0
0 0
1 0
1 1

예제 출력 

7

해설 및 후기

피타고라스의 정리를 이용해 간단히 풀 수 있다. 세 점을 마치 조합처럼 뽑은 뒤, 그 점들간의 거리의 제곱을 각각 구하고, 가장 긴 값에 대해 나머지 두 값의 합과 같다면 세 점들로 이루어지는 삼각형은 직각삼각형이다.

제출 코드 

import sys
from itertools import combinations
n = int(sys.stdin.readline().rstrip())
c = []
cnt = 0
def isRight(a,b,c):
    ab = ((a[0]-b[0])**2+(a[1]-b[1])**2)
    bc = ((b[0]-c[0])**2+(b[1]-c[1])**2)
    ca = ((c[0]-a[0])**2+(c[1]-a[1])**2)
    if(ab == bc+ca or bc == ab+ca or ca == ab+bc):
        return True
    else:
        return False

for i in range(n):
    c.append(list(map(int,sys.stdin.readline().rstrip().split())))
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1, n):
            if(isRight(c[i],c[j],c[k])): cnt+=1


print(cnt)