[백준] 2166번 다각형의 면적 C++ 코드

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int n;

double res, x, y, r;
vector<pair<double, double>> v;

// 신발끈 공식. 오목한 다각형이 있을 수 있으므로 절대값은 마지막에 적용

double go(double x, double y, double x2, double y2, double x3, double y3) {
    return (x*y2 + x2*y3 + x3*y - x2*y - x3*y2 - x*y3)*0.5;
}

int main() {
    cin >> n;
    cout << fixed;
    cout.precision(1);
    for(int i = 0; i < n; i++) {
        cin >> x >> y;
        v.push_back({x, y});
    }
    double stdx = v[0].first;
    double stdy = v[0].second;
    for(int i = 2; i < n; i++) {
        res += go(stdx, stdy, v[i - 1].first, v[i - 1].second, v[i].first, v[i].second);
    }
    cout << abs(res) << '\n';
    return 0;
}

풀이

한 점을 기준으로, 삼각형의 넓이를 구한 후 그 개수를 더해주는 방식으로 접근했다. 삼각형의 넓이는 신발끈 공식을 이용했다. 처음엔 점과 직선사이의 거리를 구해야하나... 싶었는데 신발끈 공식이 있다는 걸 기억했다. 고등학교 졸업한지 꽤 돼서 애먹을 뻔 한 문제.

참고. 정렬을 하면 안되는 이유

다각형의 면적을 계산할 때는 꼭지점들이 주어진 순서대로 배열되어 있어야 한다. 꼭지점들이 다각형의 경계를 따라 순서대로 주어져야 하는데, 정렬을 하게 되면 이러한 순서가 유지되지 않게 된다.

Shoelace 공식(사선 공식)은 꼭지점들이 다각형의 경계를 따라 순서대로 주어져 있다는 가정 하에 작동한다. 꼭지점들을 좌표 순서대로 정렬하면 면적 계산에 필요한 순서가 유지되지 않으므로 올바른 결과를 얻을 수 없다.