문제 링크: https://www.acmicpc.net/problem/2166

Thumbnail: Photo by Joel Filipe (Unsplash)

CCW를 응용해 다각형의 면적을 계산하는 문제입니다.

풀이

다각형의 면적?

다각형을 이루는 각 점의 좌표가 순서대로 주어질 때, 그렇게 만들어진 다각형의 면적을 구하는 문제입니다. 이전에 CCW 문제에서, CCW 알고리즘을 통해 유도된 식은 사선 공식과 동일하며, 이를 활용해 삼각형의 넓이를 구할 수 있다고 했습니다.

이번 문제에서는 CCW를 활용해 삼각형의 넓이를 구하고, 그 넓이의 합으로 전체 다각형의 면적을 구하는 방법을 사용합니다.

CCW를 활용해 삼각형의 넓이 구하기

먼저, CCW를 활용해 삼각형의 넓이를 구해봅시다.

CCW는 두 벡터의 외적을 활용하는 알고리즘입니다. 세 점 A, B, C에 대해 두 벡터 $\vec{AB}, \vec{AC}$의 외적을 구해봅시다.

$\vec{a} \times \vec{b} = (|\vec{a}||\vec{b}|sin{\theta}) \cdot \vec{n}\), \((0 \le \theta \le \pi)$

식을 자세히 보면, 삼각형의 넓이 공식인 $\frac{1 2}\left\vec{a}\right \left\vec{b}=right sin \theta$을 떠올릴 수 있습니다!

CCW에서도 결국 두 벡터의 외적을 사용하므로, CCW의 계산 결과를 2로 나누기만 하면 두 벡터로 이루어진 삼각형의 면적이 됩니다!

삼각형을 겹쳐서 전체 다각형의 넓이 구하기

다음과 같은 다각형이 주어졌다고 가정해 봅시다. 적절한 선을 그어, 전체 다각형을 여러 개의 삼각형으로 바꿔봅시다.

전체 다각형에서 삼각형 $P_{1}P_{2}P_{3}$와 $P_{1}P_{3}P_{4}$을 찾았습니다.

형태를 보니, $P_{1}P_{2}P_{3}$에서 $P_{1}P_{3}P_{4}$을 빼면 전체 면적이 나올 것 같습니다. 여기서 CCW를 활용할 수 있습니다.

CCW는 세 점의 방향 관계를 구하는 알고리즘입니다. 세 점이 반시계 방향으로 배열되어 있다면 양수, 시계 방향으로 배열되어 있다면 음수 값을 얻을 수 있었습니다.
그렇다면, CCW 값을 2로 나눌 뿐인 삼각형의 넓이 또한 세 점의 방향 관계에 따라 양수 또는 음수 값으로 구해질거라 예상해볼 수 있습니다.

위 예시에서, $P_{1}P_{2}P_{3}$은 세 점이 반시계 방향으로 배열되었으니 양수 넓이를 가질 것이고, $P_{1}P_{3}P_{4}$은 세 점이 시계 방향으로 배열되었으니 음수 넓이를 가질 것입니다.

따라서, 단순히 $P_{1}P_{2}P_{3}$와 $P_{1}P_{3}P_{4}$ 각각의 넓이를 CCW로 구하고, 모두 더한 값을 전체 다각형 $P_{1}P_{2}P_{3}P_{4}$의 넓이로 판단할 수 있습니다! 단순히 CCW로 계산한 각 부분 삼각형의 넓이를 더하기만 하면, 알아서 더할 면적은 더하고 뺄 면적은 빼서 계산되기 때문입니다.

다만, 전체 부분 삼각형의 합은 절댓값을 취해야 합니다. 전체 다각형의 점이 반시계 방향으로 배열되어 있다면 다각형의 면적은 양수로 계산되지만, 시계 방향으로 배열되어 있다면 반대로 음수 값이 구해지기 때문입니다. 입력 데이터가 반시계 방향인지 시계 방향인지는 명시되지 않았으므로, 절댓값을 취해 항상 양수로 다뤄주면 됩니다.

cf) 파이썬의 반올림 문제

파이썬의 경우, 흔히 생각하는 사사오입과는 다른 오사오입 방식을 사용합니다. 따라서 통상적인 round() 함수를 사용하면 반올림 된 값이 기대와는 달라, 오답을 받을 수 있습니다.

이를 해결할 수 있는 방법 2가지를 알려드리겠습니다 😄

1. decimal모듈 활용

import decimal
# decimal 모듈의 반올림 방식을 사사오입으로 재정의합니다.
decimal.getcontext().rounding = decimal.ROUND_HALF_UP

# 반올림하려는 값을 decimal.Decimal 객체로 변환한 뒤 round 함수를 사용합니다.
print(round(decimal.Decimal(ans)))

2. 간단한 꼼수

print(round(ans + 0.00000001)) # 그냥 오사오입 조건에서도 반올림이 되도록 적당히 작은 값을 더하면 됩니다.

전체 코드

from decimal import getcontext, ROUND_HALF_UP, Decimal
input = open(0).readline
getcontext().rounding = ROUND_HALF_UP

N = int(input())
coords = [tuple(map(int, input().split())) for _ in range(N)]
base_x, base_y = coords[0]

surface = 0
for i in range(1, N - 1):
    # CCW
    vec1_x = coords[i][0] - base_x
    vec1_y = coords[i][1] - base_y
    vec2_x = coords[i + 1][0] - base_x
    vec2_y = coords[i + 1][1] - base_y
    surface += vec1_x * vec2_y - vec2_x * vec1_y

print(round(Decimal(abs(surface) / 2), 1))