[SWEA 26502] 쉬운 삼각형 [Python]

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

요약

• N개의 점 중 3점을 골라, 두 변이 X, Y 축에 평행하는 삼각형의 최대 넓이를 구하자. 

---

풀이 과정

삼각형의 조건과 좌표 관계

문제에서 요구하는 삼각형은 두 변이 각각 X, Y 축에 평행해야 합니다. 이 조건을 만족하려면 해당 삼각형은 직각삼각형이어야 하며, 세 꼭짓점의 좌표는 다음과 같은 관계를 가집니다.

• 직각을 이루는 꼭짓점: ($x_1$, $y_1$)
• $x$축에 평행한 변을 만드는 점: ($x_2$, $y_1$)
• $y$축에 평행한 변을 만드는 점: ($x_1$, $y_2$)

 

전처리 - 중심점과 같은 선상의  좌표 선택

N개의 점을 하나씩 "직각을 이루는 꼭짓점(pivot)"으로 가정했을 때, 최대 넓이를 얻으려면 중심점과 같은 선상에 있는 점들 중 가장 멀리 떨어진 점을 선택해야 합니다.

이를 위해 각 좌표출별로 최소/최대 좌표를 미리 저장해두면 매번 전체 좌표를 순회할 필요가 없습니다.

def solve():
    y_bounds_by_x = defaultdict(lambda: [0, 0])
    x_bounds_by_y = defaultdict(lambda: [0, 0])
    for x, y in points:
        y_bounds_by_x[x][MAX] = max(y_bounds_by_x[x][MAX], y)
        y_bounds_by_x[x][MIN] = min(y_bounds_by_x[x][MIN], y)
        x_bounds_by_y[y][MAX] = max(x_bounds_by_y[y][MAX], x)
        x_bounds_by_y[y][MIN] = min(x_bounds_by_y[y][MIN], x)

 

방금 구한 양수/음수 좌표와 pivot에 대해 절대값이 가장 큰 거리를 찾으면 됩니다.

    max_area = 0
    for x, y in points:
        min_x, max_x = x_bounds_by_y[y]
        min_y, max_y = y_bounds_by_x[x]
        width = max(abs(x - min_x), abs(x - max_x))
        height = max(abs(y - min_y), abs(y - max_y))
        max_area = max(max_area, width * height)

    return max_area

 

문제에서 삼각형 넓이에 2를 곱한 값을 요구하므로, 밑변과 높이를 곱한 값을 그대로 출력하면 됩니다.

 

성능 분석

• 시간 복잡도: $O(N)$
• 제출결과: Pass / 79ms / 59,008kb

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/SW%20Expert%20Academy/D3/26502.py

problem-solving/SW Expert Academy/D3/26502.py at main · rogi-rogi/problem-solving