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

[문제]

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

2차원 평면상에 N개의 점으로 이루어진 다각형이 존재할 때, 이 다각형의 면적을 구하는 문제이다.

[사용 알고리즘]

수학

[풀이 핵심]

• 이 문제는 신발끈 공식이라는 고등수학을 알고 있어야 수월하게 해결할 수 있다.

위 공식이 신발끈 공식이다. 신발끈 공식은 2차원 평면위에 존재하는 삼각형의 면적을 구하는 공식이다.

• 위 공식을 이용해서 2차원 평면상의 다각형을 전부 삼각형으로 분할하여 면적을 구하고 더하는 방식으로 해결했다.

문제만 보면 정말 간단해 보이는데 신발끈 공식을 모르면 굉장히 난감해지는 문제이므로 수학공식도 공부하자...

[코드]

//boj2166번_다각형의 면적_수학

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

using namespace std;

struct dot {
	double x;
	double y;
};

int main() {
	int N;
	cin >> N;

	vector<dot> v;

	for (int i = 0; i < N; i++) {
		double a, b;
		cin >> a >> b;

		dot d;
		d.x = a;
		d.y = b;

		v.push_back(d);
	}

	v.push_back(v.front());

	double result = 0;

	for (int i = 0; i < N; i++) {
		result += ((v[i].x * v[i + 1].y) - (v[i + 1].x * v[i].y)) / 2.0;
	}

	cout << fixed;
	cout.precision(1);

	cout << abs(result);

	return 0;
}