[2166] 다각형의 면적

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

2166 - 다각형의 면적

본문

2차원 평면상에 $N$($3 \leq N \leq 10\,000$)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$이 주어진다. 다음 $N$개의 줄에는 다각형을 이루는 순서대로 $N$개의 점의 $x, y$좌표가 주어진다. 좌표값은 절댓값이 $100\,000$을 넘지 않는 정수이다.

출력

첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

문제 조건이 다각형이다. 근데 이게 전체적으로 볼록한지, 아니면 오목한 부분이 있는지는 모른다. 그래서 그냥 빙 돌아가면서 전체 넓이를 계산하는 것은 불가능하다.

그러면 취할 수 있는 방법이 하나 있다. 다각형은 여러개의 삼각형으로 쪼갤 수 있다는 것. 한 점을 기준으로 다른 점들에 모두 선을 그으면 삼각형들이 만들어진다. 이 삼각형들의 넓이를 모두 더하면 최종 다각형의 넓이가 나올 것이다. 그럼 삼각형들의 넓이만 구해낼 수 있으면 된다.

삼각형의 넓이는 CCW를 이용하면 된다. CCW가 두 벡터의 외적값을 반환하는데, 이것이 두 벡터로 만들 수 있는 평행사변형의 넓이와 같기 때문에, 삼각형은 그것을 2로 나눈 값을 넓이로 생각할 수 있다. 이 값들을 모두 더하면 전체 다각형의 넓이를 구할 수 있다.

다각형이 볼록하지 않은 부분에 대해서는 어떻게 하냐고 생각할 수 있는데, 오목한 부분에 대해서는 CCW값이 반대 부호로 나온다. 실제로 삼각형을 그려보다보면 오목한 부분에서는 겹치는 부분이 있는데, 그것들의 처리도 CCW가 알아서 해준다는 느낌.

• 참고 알고리즘 : CCW

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 22

#include <stdio.h>

typedef long long ll;
typedef struct Node {
    ll x, y;
} ND;

#define MAX_IDX 10000
ND arr[MAX_IDX];
int n;

#define abs(x) (((x) < 0) ? (-(x)) : (x))

double getOuterProduct(int i, int j) {
#define FIRST 0
    ND a = (ND){arr[i].x - arr[FIRST].x, arr[i].y - arr[FIRST].y};
    ND b = (ND){arr[j].x - arr[FIRST].x, arr[j].y - arr[FIRST].y};
    return (double)(a.x * b.y - b.x * a.y);
}

int main() {
    scanf("%d", &n);
    double ans = 0.0;
    scanf("%lld %lld", &arr[0].x, &arr[0].y);
    scanf("%lld %lld", &arr[1].x, &arr[1].y);

    for (int i = 2; i < n; ++i) {
        scanf("%lld %lld", &arr[i].x, &arr[i].y);
        ans += (getOuterProduct(i - 1, i) / 2.0);
    }

    printf("%.1lf", abs(ans));
    return 0;
}