[SWEA] 26502. 쉬운 삼각형

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AZz7DObKASzHBIRj&categoryId=AZz7DObKASzHBIRj&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

나의 방식 

삼각형의 한 변은 x축에 평행해야 하고, 다른 한 변은 y축에 평행해야 한다. 라는 조건에서 직각 삼각형이 요구됨을 알 수 있다. 

따라서 나는 점들 중 하나의 점을 꼭짓점이라 가정할 때, 그 점을 기준으로  x축으로 평행한 점과 y축으로 평행한 점을 찾아 삼각형의 넓이를 구하고 그에 대한 최대값을 구하는 방식으로 접근했다. 

 

따라서, p1, p2, p3 이 삼각형의 세 점이라 할 때 세 개의 점이 각각 꼭짓점일 경우를 계산해서 절댓값을 통해 넓이를 구하려고 했다.

def is_triangle(p1, p2, p3):
    # p1이 직각 꼭짓점
    if p1[0] == p2[0] and p1[1] == p3[1]:  # p1-p2 세로, p1-p3 가로
        h = abs(p2[1] - p1[1])
        w = abs(p3[0] - p1[0])
        return h * w
    
    if p1[1] == p2[1] and p1[0] == p3[0]:  # p1-p2 가로, p1-p3 세로
        w = abs(p2[0] - p1[0])
        h = abs(p3[1] - p1[1])
        return h * w
    
    # p2가 직각 꼭짓점
    if p2[0] == p1[0] and p2[1] == p3[1]:  # p2-p1 세로, p2-p3 가로
        h = abs(p1[1] - p2[1])
        w = abs(p3[0] - p2[0])
        return h * w
    
    if p2[1] == p1[1] and p2[0] == p3[0]:  # p2-p1 가로, p2-p3 세로
        w = abs(p1[0] - p2[0])
        h = abs(p3[1] - p2[1])
        return h * w
    
    # p3가 직각 꼭짓점
    if p3[0] == p1[0] and p3[1] == p2[1]:  # p3-p1 세로, p3-p2 가로
        h = abs(p1[1] - p3[1])
        w = abs(p2[0] - p3[0])
        return h * w
    
    if p3[1] == p1[1] and p3[0] == p2[0]:  # p3-p1 가로, p3-p2 세로
        w = abs(p1[0] - p3[0])
        h = abs(p2[1] - p3[1])
        return h * w
    
    return 0

 

그리고 3중 반복문을 통해 (i, j, k) 의 경우로 삼각형 넓이를 구하고 최대값을 갱신하는 방식을 사용했다.

T = int(input())
for test_case in range(1, T + 1):
    case = int(input())
    p = []
    
    for _ in range(case):
        x, y = map(int, input().split())
        p.append((x, y))
    
    max_area = 0
    
    for i in range(case):
        for j in range(i+1, case):
            for k in range(j+1, case):
                area = is_triangle(p[i], p[j], p[k])
                max_area = max(max_area, area)
    
    print(max_area)

 

다른 방식 

내 방식이 상당이 비효율적이라고 느껴 다른 답안을 보다가,

SW Expert Academy 슈 님의 답안을 보고 되게 좋은 방식이라고 느꼈다. 

 

각 점을 직각 꼭짓점으로 가정하고 

• 같은 x좌표를 가진 점들 중 가장 먼점을 찾아 y 방향의 최대 길이를 계산
• 같은 y좌표를 가진 점들 중 가장 먼점을 찾아 x 방향의 최대 길이를 계산

하면 그 점을 꼭짓점으로 하는 최대 직각삼각형이 만들어지는 원리이다.

 

나의 경우, 모든 3점의 조합을 체크해야 하지만 이 답안의 경우 각 점마다 최댓값만 찾으면 되므로 훨씬 효율적이라고 할 수 있다.