[BOJ / C++] 2166 - 다각형의 면적

백준 문제 링크 : 2166 - 다각형의 면적

문제

풀이

다각형의 모든 꼭짓점의 넓이가 주어지는 경우, 신발끈 정리(또는 가우스 면적 공식, 사선 공식 등..으로 불림)로 넓이를 구할 수 있습니다. 신발끈 정리란..

이렇게 생긴 행렬 계산을 하기 때문에 신발끈 정리라고들 부릅니다.
자세히 들여다보면 그냥 외적입니다.

행렬 계산은
(빨간 화살표로 이어진 두 좌표의 곱들의 합) + (파란 화살표로 이어진 두 좌표의 곱들의 합)
에 절댓값을 씌우고 2로 나누면 됩니다. 공식으로 쓰면

아래와 같이도 생각해볼 수 있습니다. 다각형을 다음과 같이 여러 삼각형으로 분할한다고 생각해봅시다.

$n$각형에 대해, 한 꼭짓점 $P_1$을 잡고, 남은 점들 중 임의의 두 점$P_2, P_3$을 잡으면 생기는 삼각형을 그립니다. 이 과정을 $P_n$까지 반복하면 $n-2$개의 삼각형으로 분할되고, 이 모든 삼각형들의 넓이를 구하여 모두 더하면 다각형의 넓이입니다.

신발끈 정리에서 보았듯이, $(x_1,y_1),(x_2,y_2),(x_3,y_3)$을 꼭짓점으로 하는 삼각형의 넓이는
$|(x_1y_2 + x_2y_3 + x_3y_1) - (y_1x2 + y_2x_3 + y_3x_1)|/2$

그런데 한 가지 마음에 걸리는 점은.. 다각형은 위 그림처럼 볼록하게만 생기지 않습니다.

이렇게도 생길 수 있겠죠?
간단히 이 경우까지 포괄하여 계산할 수 있는데, 사실 아래와 같이 계산하면 이런 경우까지 잘 계산이 됩니다. 각 삼각형들의 넓이를 $S_1, S_2, ... , S_n$이라하면
$|S_1 + S_2 + ... + S_n|$

간단히 말하면.. 오목한 부분을 차지하는 삼각형의 넓이는 음수로 계산되어 그만큼 넓이에서 제외되기 때문입니다. 아래의 사진 출처에 더 자세한 설명이 있습니다.
사진 출처

이제 신발끈정리와 그 유도법도 알아봤으니 코드를 작성해야겠습니다.
이 때 주의할 점은, 아무래도 넓이 계산을 할 때에는 자료형을 대충 정하면 오버플로우가 발생하기 십상입니다. 저같은 경우 각 좌표들은 long long으로 저장하고 넓이 계산은 long double로 했습니다.

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

using namespace std;

int main () {
	int n;
	cin >> n;
	vector<pair<long long,long long>>pos(n+1);
	for(int i=0;i<n;i++) scanf("%lld %lld", &pos[i].first, &pos[i].second); 
	long double area = 0;
	for(int i=0;i<n;i++) {
		long double d1 = pos[i].first * pos[(i+1)%n].second;
		long double d2 = pos[(i+1)%n].first * pos[i].second;
		area += (d1 - d2)/2;
	}
	printf("%.1Lf", abs(area));
}

위 코드는 신발끈정리로만 계산하는 경우입니다. 처음에는 아래와 같이 삼각형들을 나누어 계산하는 코드를 작성해봤습니다. 확실히 위와 같이 짜는게 훨씬 간단하긴 합니다

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

using namespace std;

int main () {
	int n;
	cin >> n;
	vector<pair<long long,long long>>pos(n+1);
	for(int i=0;i<n;i++) scanf("%lld %lld", &pos[i].first, &pos[i].second); 
	//두 점을 잡고, (0과 1) 2부터 각 세 점을 이은 삼각형의 넓이를 모두 더하기
	long double area = 0;
	for(int i=1;i<n-1;i++) {
		long long x1 = pos[0].first, y1 = pos[0].second;
		long long x2 = pos[i].first, y2 = pos[i].second;
		long long x3 = pos[i+1].first, y3 = pos[i+1].second;
		long double d1 = x1*y2 - x2*y1;
		long double d2 = x2*y3 - x3*y2;
		long double d3 = x3*y1 - x1*y3; 
		area += (d1 + d2 + d3)/2;
	}
	printf("%.1Lf", abs(area));
}

신발끈 정리에 대한 더 자세한 내용은 여기 << 나무위키