[백준 2166번 C/C++] 다각형의 면적

 

[백준 2166번 C/C++] 다각형의 면적

 

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

2166번: 다각형의 면적

---

 

해결전략

 

기하학. 다각형의 넓이

 

---

 

실수한 부분 - 주어진 점들의 순서를 조작하면 안 된다

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip> // 소수점 자리 설정을 위한 헤더. setprecision() 사용가능
using namespace std;

struct Coor{
	double x; double y;
};

bool Compare(Coor& a, Coor& b){ 실수한 부분. 다각형을 이루는 순서대로 입력이 주어지기 때문에 점들을 정렬하면 안 된다.
	if (a.y == b.y)
		return a.x > b.x;

	return a.y > b.y;
}

int n;
vector<Coor> v;

double Area(int idx)
{
	double x1 = v[idx].x;
	double y1 = v[idx].y;
	double x2 = v[idx+1].x;
	double y2 = v[idx+1].y;

	return (y2 - y1) * (x1 + x2) / 2;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n+1);
	for(int i = 0; i < n; i++){
		cin >> v[i].x >> v[i].y;
	}
	sort(v.begin(), v.end(), Compare); // 실수한 부분. 다각형을 이루는 순서대로 입력이 주어지기 때문에 점들을 정렬하면 안 된다. 

	v[n].x = v[0].x;
	v[n].y = v[0].y;

	double answer = 0.0f;
	for(int i = 0; i < n; i++)
	{
		answer += abs(Area(i));
	}

	cout << fixed << setprecision(1) << answer;

	return 0;
}

 

다각형을 이루는 순서대로 입력이 주어지기 때문에 점들을 정렬하면 안 된다.

---

 

 

정답코드

 

#include <iostream> 
#include <vector> 
#include <iomanip> // 소수점 자리 설정을 위한 헤더
using namespace std; 

struct Coor{ 
	double x; double y;
};

int n; // 점의 개수
vector<Coor> v; // 좌표를 저장할 벡터

// 시계방향 기준으로, i번째 점과 i+1번째 점으로 이루어진 사다리꼴의 넓이를 계산하는 함수
double Area(int idx) 
{
	double x1 = v[idx].x;
	double y1 = v[idx].y;
	double x2 = v[idx+1].x;
	double y2 = v[idx+1].y;

	return (y1 - y2) * (x1 + x2) / 2; 
}

int main(){ 
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0);

	cin >> n; 
	v.resize(n+1); 
	for(int i = 0; i < n; i++){
	 >> v[i].x >> v[i].y;
	}

	v[n].x = v[0].x; // n번째 점의 좌표를 0번째 점의 좌표와 동일하게 설정
	v[n].y = v[0].y; // 이렇게 하면 마지막 점과 첫번째 점을 연결하는 사다리꼴의 넓이도 계산할 수 있음

	double answer = 0.0f; 
	for(int i = 0; i < n; i++) 
	{
		answer += Area(i); // 각 사다리꼴의 넓이를 합하여 면적을 계산
	}

	cout << fixed << setprecision(1) << abs(answer); // 면적의 절대값을 소수점 아래 한 자리까지 출력

	return 0;
}

 

다각형의 면적을 구하기 위해 '사다리꼴의 넓이'를 이용하였다.

사다리꼴의 넓이를 구하는 공식:
(윗변 + 아랫변) * 높이 / 2

이 코드에서는 x축을 기준으로 한 사다리꼴의 넓이를 계산한다. 즉, 각 점의 y 좌표를 사다리꼴의 '변'으로, 두 점 사이의 x 좌표의 차를 '높이'로 생각한다.

(y1 + y2) * (x1 - x2) / 2

시계 방향으로 점을 순회하면서 면적을 계산한다. 이 때문에, 사다리꼴의 넓이가 음수로 계산될 수 있다.
따라서, 최종 면적을 계산할 때는 abs(answer)를 사용하여 면적의 절대값을 구하게 된다. 이렇게 하면 시계방향, 반시계방향에 상관없이 항상 양수인 면적을 얻을 수 있다.

---

 

참고 사이트

 

https://www.mathopenref.com/coordpolygonarea2.html

Area of a polygon algorithm - Math Open Reference

 

---