[G5] 백준 2166번 다각형의 면적 C++ 기하학, 신발끈 공식, 슈메르카우스키의 공식

리뷰

 

다각형의 면적을 구하는 방법은 또 처음 알았다! 슈메르카우스키의 공식... 이세상엔 천재가 많다.

덕분에 좌표 평면상에서의 다각형의 공식을 구하는 방법은 잊지 않을 것 같다!

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

 

문제 풀이

1. 꼭지점의 개수 n과, 정답용 변수 ans, 좌표 구조체 Pos와 그의 배열 poses를 전역 변수로 세팅한다.
2. n값을 입력 받고 n개의 꼭지점 좌표를 받아와 poses배열에 추가해 준다.
3. n - 1번째 까지의 꼭지점을 탐색하며 xi*yi+1 - yi*xi+1 을 구해준 뒤 ans에 더해준다.
4. 최종적으로 0번째와 n - 1번째 인덱스의 꼭지점을 처리해 준 뒤 ans를 2로 나누어 준다.
5. ans에 절댓값을 씌운 뒤 소숫점 1자리까지 반올림하여 출력해 주면 된다.

 

 

참고 사항

슈메르카우스키의 공식(또는 신발끈 공식)

2차원 좌표계에서, 꼭짓점이 n각형인 면적 A는 다음과 같이 계산 된다고 한다.

 

해당 공식을 보면 for문을 통해 i와 i + 1번째의 꼭지점을 가져다가 적절한 수식을 만들어 답을 구할 수 있음을 알 수 있다.

시그마를 사용하지 않은 식은 아래와 같다.

 

추가로, 처음 채점 시 좌표를 입력 받을때 정수로 받아와 틀렸습니다가 노출되었는데 아마 x, y좌표가 둘다 10만일때 둘을 곱하면 정수형 타입에 오버플로우가 생겨서 그런 것 같다.

좌표도 동일하게 double 타입을 사용하거나 long long 타입을 사용하는 것을 추천한다.

 

 

정답 코드

#include<iostream>

using namespace std;

int n;
double ans = 0;

struct Pos {
	double x, y;
};

Pos poses[10000];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		double x, y; cin >> x >> y;
		poses[i] = { x, y };
	}

	for (int i = 0; i < n - 1; i++) {
		Pos pos1 = poses[i];
		Pos pos2 = poses[i + 1];
		double x1 = pos1.x, y1 = pos1.y, x2 = pos2.x, y2 = pos2.y;
		ans += x1 * y2 - y1 * x2;
	}
	ans += poses[n - 1].x * poses[0].y - poses[n - 1].y * poses[0].x;
	ans /= 2;
	printf("%.1f", abs(ans));
}