백준 2166 다각형의 면적 문제 풀이

문제 파악하기

입력으로 다각형 꼭짓점의 좌표를 제시합니다. 이 좌표만을 사용하여 다각형의 면적을 구해야합니다.

꼭짓점은 다각형을 구성하는 순서대로 제공하므로, 굳이 순서를 변경하여 문제의 의도와 다른 다각형을 고려할 필요는 없습니다.

문제 풀어보기

문제에서 제시하는 도형은 다각형이기만 무엇이든 가능하므로 제시되는 도형의 유형은 매우 다양합니다.

단순한 삼각형, 사각형 이상으로 별, 속이 빈 다각형 등 단순 면적 공식으로 구하기에는 복잡한 과정을 거쳐야 하는 도형도 처리해야합니다. 즉, “가로 * 세로”로 대표되는 일반적인 면적 공식은 통하지 않습니다.

신발끈 공식

신발끈 공식은 좌표평면 상에 존재하는 모든 다각형의 면적을 구할 수 있는 범용적인 공식입니다.

def compute(arr: list[tuple[int]]) -> float:
    sums = 0
    for i in range(n):
        sums += arr[i % n][0] * arr[(i + 1) % n][1]
        sums -= arr[(i + 1) % n][0] * arr[i % n][1]
    return abs(sums / 2)

주의할 점은, 신발끈 공식은 벡터의 외적을 활용하므로 좌표의 시계/반시계 방향 정렬 여부에 따라 결과값이 양수 혹은 음수로 계산될 수 있습니다. 신발끈 공식의 정의대로 절댓값 처리를 해주지 않으면 한 변의 길이가 허수인 다각형의 면적을 구하게 됩니다.

답안 구현

2166 Python 답안