[백준-2166] 다각형의 면적

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <tuple>
#include <cmath>

using namespace std;
typedef pair<long double, long double> pii;
int n, cnt = 0, a, b;
priority_queue<int, vector<int>, greater<int>> pq;
vector<pii> v;
int main()
{
    int n;
    long double a, b;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%Lf %Lf", &a, &b);
        v.push_back({ a, b });
    }
    long double x1, y1, x2, y2, x3, y3;
    x1 = v[0].first;
    y1 = v[0].second;
    long double res = 0;
    for (int i = 1; i < v.size(); i++) {
        x2 = v[i - 1].first;
        y2 = v[i - 1].second;
        x3 = v[i].first;
        y3 = v[i].second;
        res += (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3);
    }
    printf("%.1Lf", abs(res/2));
    return 0;
}

수학적 풀이가 필요한 문제이다...

일단 일반적으로 3개의 점이 주어진 삼각형을 구하는 공식은 오른쪽과 같다.

이 때 너비를 구할 때 절대값을 해주는 이유는 외적에서 방향성을 통해 양수 값의 너비를 구하기 위함이다. 보통 이런식으로 문제를 풀면 된다고 생각한다.

하지만 이 문제의 경우 주어진 점을 순서대로 이은 후에 마지막에 나타나는 다각형의 너비를 구하는 문제이므로 점을 이쁘게 모두 이은 다각형 모양이 아닌 순서가 약간 뒤바뀌어 이었을 때 나올 수 있는 여러개의 다각형의 너비를 구하는 식으로 풀어야 한다.

따라서 위의 공식에서 절대값을 뺀 값들을 계속 더하게 되면 어느 곳에서는 음수인 너비가 다른 곳에서 양수의 값으로 상쇄되는 식으로 계산되어 결국 마지막에 제대로 된 너비를 구할 수 있게 된다.... 이해가 잘 안된다면 너비 외적 구하기 검색 ㄱㄱ..

 

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

2166번: 다각형의 면적