[BOJ] 2166번 다각형의 면적 (C++)

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

2166번: 다각형의 면적

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n;
vector<pair<int, int>> v;

long double solve(int i, int j){
	long double x1 = v[0].first, y1 = v[0].second;
	long double x2 = v[i].first, y2 = v[i].second;
	long double x3 = v[j].first, y3 = v[j].second;
	
	return (x1 * y2 + x2 * y3 + x3 * y1 - x2 * y1 - x3 * y2 - x1 * y3) / 2;
}

int main() {
	cin >> n;
	for(int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		v.push_back({a, b});
	}
	
	long double ans = 0;
	for(int i = 1; i < n - 1; i++){
		ans += solve(i, i + 1);
	}
	cout << fixed;
	cout.precision(1);
	cout << abs(ans);
	return 0;
}

 

다각형을 삼각형으로 쪼개고 삼각형 넓이는 신발끈 공식으로 구했다.

신발끈 공식은 삼각형의 꼭짓점의 좌표를 알면 넓이를 구할수 있는 공식이다. 

 

 

예를들어

반복문을 돌면서 a-b-c의 넓이 + b-c-d의 넓이 … + a-e-f의 넓이 계산을 해주면 전체 도형의 넓이를 구할 수 있다.
넣는 순서에 따라 결과값이 음수로 나올수도 있기 때문에 최종 결과값에 절대값을 붙여줘야 한다.

이런 경우에도 그냥 첫번째 계산과 마찬가지로 계산해주면 된다. 왜 그런지 생각해보면 a-b-c의 넓이를 구하고 거기다 a-c-d의 넓이를 더하게되면 a-b-c의 넓이과 a-c-d의 넓이는 서로 다른 부호를 갖게 되어 전체 도형에서 오목하게 들어간 부분을 빼주는 것이 된다.