[백준 1711번] 파이썬 - 직각삼각형

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

1711번: 직각삼각형

 

 

 

# 조건

• 2차원 평면에 N개의 점
• 세 점을 골랐을 때, 직각삼각형이 몇 개있는지를 구하여라.

 

# 접근 방법

• 피타고라스 정리
  • c^2 = a^2 + b^2
• 두 점 사이의 거리를 구해서 가장 긴 변이 빗변이 된다.
• 빗변을 구한 후 피타고라스 정리를 이용하여 직각삼각형인지 판별

 

# 브루트 포스 - 시간초과

N = int(input())  
  
dot = [list(map(int, input().split())) for _ in range(N)]  
cnt = 0  
for i in range(N-2):  
    for j in range(i+1, N):  
        for k in range(j+1, N):  
            # 각 점사이의 거리를 구해준 후 리스트에 넣어준다.  
            a = ((dot[i][0] - dot[j][0]) ** 2 + (dot[i][1] - dot[j][1]) ** 2) ** 0.5  
            b = ((dot[i][0] - dot[k][0]) ** 2 + (dot[i][1] - dot[k][1]) ** 2) ** 0.5  
            c = ((dot[k][0] - dot[j][0]) ** 2 + (dot[k][1] - dot[j][1]) ** 2) ** 0.5  
            dist = [a,b,c]  
            result = max(dist)  
            dist.remove(result)  
            rest = dist[0]**2 + dist[1]**2  
  
  
            if round(rest,2) == round(result**2,2):  
                cnt += 1  
  
  
print(cnt)

 

 

# pypy 통과

# 1711번 직각 삼각형
import sys
input = sys.stdin.readline

N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
cnt = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            # 인덱스에 해당하는 좌표값을 먼저 변수에 넣어준다.
            dot1, dot2, dot3 = points[i], points[j], points[k]
            # 각 변의 길이
            d1 = (dot1[0]-dot2[0])**2 + (dot1[1]-dot2[1])**2
            d2 = (dot2[0]-dot3[0])**2 + (dot2[1]-dot3[1])**2
            d3 = (dot3[0]-dot1[0])**2 + (dot3[1]-dot1[1])**2
            # 피타고라스 정리
            if 2*max(d1,d2,d3) == d1+d2+d3:
                cnt += 1
print(cnt)

 

 

• 내부에서 계산을 해줄 때 미리 변수에 인덱스에 해당하는 값을 해주니 시간이 더 빨라졌다.