c++ 백준_2166_"다각형의 면적"

 

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

2166번: 다각형의 면적

 

처음 접근한 방법은

그래픽스 시간에 배운 모든 도형은

삼각형 근사가 가능하다는 것에서 시작했다.

​

그래서 다각형을 삼각형으로 나눠

나온 모든 삼각형의 넓이를 계산하려했다.

​

처음 삼각형 넓이를 구하려고 했는 방법은

그냥 다 때려박았다.

두점 사이의 좌표로 기울기를 구할 수 있으니 방정식을 구해서

그에 수직인 방정식을 구해 ..여차저차 넓이를 구할 수 있었다.

​

그래서 좌표가 주어지면

index 번호로 보았을 때,

0 - 1 - 2,

0 - 2 - 3,

0 - 3 - 4,

...

처럼 진행하려했다.

​

​

아래와 같은 도형이 있고 index 0이 해당 위치에 있다면

삼각형으로 잘 나누어지고 넓이가 구해진다.

​

​

​

근데 처음 index 가 위쪽 방향에 있다면

0 - 1 - 2 는 필요한 삼각형으로 나누어지는데

그 다음인 0 - 2 - 3이 제대로 나누어지지않았다.

​

​

​

여기서 내가 모르는 또 뭔가 쓰이는 공식이 있을 거 같아 찾아보니

세 좌표를 알면 삼각형 넓이를 구할 수 있는 외적 공식이 있었다.

https://thrillfighter.tistory.com/234

해당 공식은 세좌표를 CCW (반시계방향 기준)으로 외적을 구하면,

평행사변형의 넓이가 나오는데 그걸 반으로 나눠 삼각형의 넓이로 만드는 것이다.

​

그리고 해당 도형 좌표 0,1,2 기준으로

CCW(반시계방향) 는 0 - 2 - 1 를 좌표로 넣냐(양수 반환)

CW(시계방향)는 0 - 1 - 2 순서로 좌표(음수 반환)로 넣냐에 따라

음수 양수로 나온다.

​

ex) CCW = 0 - 2 - 1 , 1 - 0 - 2 , ...

CW = 0 - 1 - 2 , 2 - 0 - 1 , ...

​

​

내가 계속해오던

0 - 1 - 2

0 - 2 - 3

..

은 도형에 따라 다른데

해당 도형에서는 0 - 1 - 2 는 CW라서

해당 공식에 대입하면 음수값이 나온다.

​

0 - 2 - 3 은 CCW라서 양수 값이 나온다.

​

근데 아까 말했듯 0 - 2 - 3 에 해당하는 삼각형은 넓이로 필요가 없다

현재 외적 공식으로 나온 0 - 2 - 3 삼각형의 넓이는 양수로 나온다.

(이후 모두 더한 값에 절대값을 취할 예정이므로 상관없다.)

​

그리고 0 - 3 - 4 는 CW라서

음수값의 해당 삼각형의 넓이가 나온다.

그럼 |(0 - 2 - 3) 삼각형 넓이 + (0 - 3 - 4) 삼각형 넓이| 하면 아까부터 해결하지 못했던 넓이를 구할 수 있다.

​

이런 식으로 외적 공식을 사용해 나눠진 삼각형의 넓이를 모두 더하고 난 뒤

CCW 로 계산했냐, CW로 계산했냐에 따라 부호가 다르기 때문에

마지막에 절대값을 취해주면 된다.

​

​

**

기하학이란...참으로 어렵고도 신기하고도 편리하구나..

 

#include <iostream>
#include <vector>
#include <string.h>
#include <cmath>
#include <algorithm>
using namespace std;

pair<double, double> coordinate[10000];
double returnTriangleArea(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
	// (a,b) (c,d) (e,f)
	double a = A.first, b = A.second;
	double c = B.first, d = B.second;
	double e = C.first, f = C.second;

	double sum = (a * d + c * f + e * b) - (b * c + d * e + f * a);
	
	return  sum/ 2;
}

int main(void) {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int  N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> coordinate[i].first >> coordinate[i].second;
	}

	
	int base_idx = 0;;
	int before_idx = 1;

	double ans = 0;
	for (int i = 2; i < N; i ++) {

		ans += returnTriangleArea(coordinate[base_idx], coordinate[before_idx], coordinate[i]);
		before_idx = i;

	}

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

}