[C++ 백준 풀이] 2166번 : 다각형의 면적 (사선 공식, CCW 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 "2166번 : 다각형의 면적" 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Gold V 티어에 해당하며, 문제 풀이에 필요한 사선 공식과 CCW 알고리즘에 대한 개념을 다룰 것입니다.

 

 

2166번 : 다각형의 면적

 

2차원 좌표로 N개의 점의 좌표가 주어질 때, 이 점들로 이루어진 다각형의 면적을 구하는 문제입니다.

이러한 기하 면적 문제는 단순히 볼록 다각형만 주어지지는 않을 것으로 예상되기 때문에, 다양한 모양의 다각형의 면적을 일반화시켜 구할 수 있는 방법을 생각해보아야 합니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래 접은 글에 정리되어 있습니다.

#include <cstdio>
using namespace std;

int main() {
    int N;
    double coor[10005][2], sum = 0;
    scanf("%d" ,&N);
    for(int i=0; i<N; i++) scanf("%lf %lf", &coor[i][0], &coor[i][1]);
    for(int i=0; i<N-1; i++) {
        sum += 0.5 * (coor[0][0]*coor[i][1] + coor[i][0]*coor[i+1][1] + coor[i+1][0]*coor[0][1]
                        - coor[i][0]*coor[0][1] - coor[i+1][0]*coor[i][1] - coor[0][0]*coor[i+1][1]);
    }
    printf("%.1lf", sum>=0?sum:-sum);
}

 

우선 풀이를 생각해보면, 다각형을 여러 개의 삼각형으로 쪼개어 각 삼각형의 넓이를 합치는 방법이 가장 쉬워 보입니다.

삼각형의 경우 사선 공식을 통해서 세 점의 좌표만 가지고 넓이를 구할 수 있습니다.

사선 공식은 삼각형의 세 점의 좌표로 삼각형의 넓이를 구하는 공식이며, 세 점의 좌표가 (x1, y1), (x2, y2), (x3, y3)일 때 S = 1/2 * | x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2 | 로 구할 수 있습니다.

 

이제 생각해보아야 하는 점은 오목 다각형인 경우인데, 이것은 CCW 알고리즘에 의해 자동적으로 해결이 됩니다.

이것은 위의 사선 공식에서 절댓값을 없앤 경우인데, CCW 알고리즘에 의해 세 점의 방향이 반대로 배치될 경우 S 값의 부호가 반대로 나타나게 됩니다.

그렇기 때문에 각 삼각형의 넓이를 구할 때 절댓값을 처리하지 않고 계산한 뒤, sum을 구하고 마지막에만 절댓값을 붙여주면 오목한 부분은 마이너스 부호로 넓이가 계산이 되기 때문에 볼록한 부분의 넓이 - 오목한 부분의 넓이로써 정확히 다각형의 넓이만 계산이 되게 됩니다.

 

따라서 요약을 해보면, N각형의 다각형을 N-2개의 삼각형으로 쪼갠 후에 각 삼각형의 넓이를 S = 1/2 * ( x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2 )로 구하고, 이들의 합을 구하면 합하는 과정에서 오목한 부분은 마이너스 부호로 들어가서 상쇄되게 되고, 합을 구한 뒤에 절댓값을 붙여 최종 넓이를 구해주면 되는 것입니다.

 

 

위의 코드를 제출해서 채점해보면 4ms라는 길지 않은 시간에 모든 테스트케이스를 통과함을 확인할 수 있습니다.

예상 외로 고려해야 할 점이 많았으나 실제로 공식의 일반성에 의해 생각보다 간단하게 해결할 수 있었던 문제였습니다.