boj, 백준) 2166. 다각형의 면적 ( C / C++ )

1. 문제 링크

www.acmicpc.net/problem/2166

2166번: 다각형의 면적

 

2. 문제 개요

2차원 편명상에 N개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

 

 

3. 문제 힌트

외적을 사용하자. 두 벡터를 외적한 것은 두 벡터로 만들어지는 평행사변형의 넓이를 나타냄.

 

 

4. 문제 풀이

(다른 블로그에서도 좋은 풀이가 있었으나, 중요한 기초 개념인 것 같아 업로드 합니다.)

 

우선, 다각형은 엄청 찌그러질 수 있기 때문에... 크기를 쪼개고 쪼개서 넓이를 구한 뒤 그 합을 출력해야 함을 바로 유추할 수 있었다.

 

그림을 통해 아주 간단한 시나리오부터, 헷갈리는 시나리오를 확인해 보겠다.

 

 

이렇게 볼록한 다각형이 주어졌다고 해보자.

 

기준점(위의 그림에서는 0번)에서 나머지 정점들로 이어지는 벡터를 구하고 외적을 한다. 외적을 하면 평행사변형의 넓이가 나오는데, 평행사변형의 넓이를 2로 나누어 위의 그림 기준으로 (0,1,2), (0,2,3), (0,3,4), (0,4,5) 삼각형의 넓이를 구한다.

 

평행사변형

이 부분은 이해가 한 번에 팍!! 안 될 것 같다. 종이에 한번 직접 적어서 해보는 걸 추천한다.

 

한번 고려해볼 만한 예로,

복잡한 예

다음과 같은 도형이 입력으로 들어온다고 생각해보자.

 

3번까지의 영역은 위의 외적으로 구할 수 있다고 바로 생각된다. 하지만 (0, 3, 4) 삼각형을 구하면 뭔가 영역이 이상해지는 것 같이 보일 수 있다.

0,4,3 삼각형을 뺀 경우

반시계로 가다가 시계방향인 삼각형이 들어왔다. 부호가 다르기 때문에 서로 영역을 빼는 효과를 내는데,

(0,2,3) 삼각형 일부가 사라지고, 불필요한 노란색 부분의 삼각형이 빼진 것을 된 것을 볼 수 있다. 이렇게 되어서 영역을 제대로 구할 수 있는가..? 싶지만 다음 삼각형(0,4,5)을 더해보면, 

 

노란색부분(안 빼도 되는 부분인데 빼진 부분)은 자연스럽게 더해지며 상쇄되고,

정확하게 다각형의 넓이를 구할 수 있다. 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int n;
vector<pair<int, int>> v; //x,y
double ans;

long long outer_product(pair<long long, long long> x, pair<long long, long long>y) 
{
	return x.first*y.second - x.second*y.first;
}

int main()
{
	scanf("%d", &n);

	for (int i = 0; i < n; ++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		v.push_back({ x,y });
	}

	for (int i = 1; i < n - 1; ++i) {
		ans += (double)(outer_product({ v[i].first - v[0].first, v[i].second - v[0].second }, { v[i + 1].first - v[0].first, v[i + 1].second - v[0].second }) / 2.0);
	}

	printf("%.1lf", abs(ans));
	return 0;
}

 

 

6. 결과

댓글 환영입니다~