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

문제 링크

www.acmicpc.net/problem/2166

2166번: 다각형의 면적

 

풀이

어떤 삼각형의 세 좌표가 주어졌을 때, 그 삼각형의 넓이는 외적값의 절반입니다.

CCW를 구하는데도 외적이 쓰이구요. CCW에 대해선 다음 글을 참고해주세요.

CCW로 세 점의 방향성 판별하기 - 데구리 블로그

 

이걸 확장해서 다각형의 면접을 구할 때도 CCW를 사용할 수 있습니다.

한 점을 기준으로 잡고, 연속한 두 점마다 CCW의 값을 더해준 뒤, 합의 절댓값을 2로 나눠주면 됩니다.

놀랍게도 이 방법은 오목 다각형에도 예외 없이 적용됩니다.

 

 

정답 코드

#include <bits/stdc++.h>
#define ft first
#define sd second
using namespace std;
using ll = long long;

int n;
pair<ll, ll> p[10000];
ll ccw(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
	return x1*y2 + x2 * y3 + x3 * y1 - (y1*x2 + y2 * x3 + y3 * x1);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p[i].ft >> p[i].sd;
	}
    auto [x, y] = p[0];
	ll ans = 0;
	for (int i = 1; i < n - 1; i++) {
		ans += ccw(x, y, p[i].ft, p[i].sd, p[i + 1].ft, p[i + 1].sd);
	}
    ans = abs(ans);
    cout << ans/2;
    if(ans & 1) cout << ".5";
    else cout <<".0";
}