[백준/C++] 2166번: 다각형의 면적

문제

https://www.acmicpc.net/problem/2166

---

문제 요약

2차원 평면 상에 n개의 점으로 이루어진 다각형의 면적을 출력한다.

 

+ n개의 점의 x, y 좌표가 주어진다.

---

코드

#include <iostream>
#include<vector>
#include<tuple>

using namespace std;

int n;
double res;
vector<tuple<double, double>> dots;

double tri_size(double x1, double y1, double x2, double y2, double x3, double y3) {
    double ans = (x1 * y2 + x2 * y3 + x3 * y1);
    ans -= (x2 * y1 + x3 * y2 + x1 * y3);
    return ans / 2;
}

int main() {
    // 입출력 단축
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 점 좌표 입력
    cin >> n;

    for (int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;
        dots.push_back({ x, y });
    }

    // 기준 점 잡기
    double x1, y1;
    tie(x1, y1) = dots[0];

    // CCW 계산 (삼각형 크기)
    for (int i = 1; i < n - 1; i++) {
        double x2, y2, x3, y3;
        tie(x2, y2) = dots[i];
        tie(x3, y3) = dots[i + 1];

        res += tri_size(x1, y1, x2, y2, x3, y3);
    }
    
    // 소수점 첫째자리까지 출력
    cout << fixed;
    cout.precision(1);
    cout << abs(res);

    return 0;
}

---

코드 설명

2차원 평면 상의 다각형의 넓이를 구하기 위해서, 먼저 삼각형으로 나눈다.

 

삼각형의 넓이를 구하기 위해서는 CCW를 구하는 공식을 이용할 수 있다.

 

CCW란, 2차원 평면에서 점C가 선분 AB의 왼쪽에 있는지 오른쪽에 있는지 구분하는 방법이다.

 

이 때, 벡터 AB와 AC의 외적을 구하고, 부호를 점검한다.

 

A(x1, y1), B(x2, y2), C(x3, y3)인 경우

 

벡터 AB: (x2 - x1, y2 - y1)

벡터 AC: (x3 - x1, y3 - y1)

 

즉, 외적은 (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) 이다.

 

외적을 구하면, 그 크기는 선분 AB와 선분 AC로 만든 평행사변형의 넓이와 같다.

 

따라서, 2로 나누면 그 크기는 삼각형 ABC의 넓이가 된다.

 

이를 통해 고등학교 때 배웠던 신발 끈 공식을 유도할 수 있다.

 

지금까지는 볼록 다각형일 때만을 생각했을 수 있다.

 

하지만, 볼록 다각형이 아닐 경우에도 그냥 계산을 하면 된다.

 

그 이유는 볼록 다각형이 아닌 경우, 삼각형들이 서로 겹치게 된다.

 

이 때, 각 CCW를 계산하면 서로 다른 부호를 갖기 때문에 자동으로 전체 도형에서 오목하게 들어간 부분을 빼주는 것이 된다.

 

즉, 한 점을 기준으로 잡고, 두 점을 바꿔가며 CCW를 더하면 된다.

 

+ 추가로 결과값이 음수가 나올 수 있으므로, 절댓값을 출력해야한다.

---

고찰

소수점 n째자리까지 출력하기 위해서 사용되는 방법은 다음과 같다.

 

cout << fixed;

cout.precision(n);