[BOJ] 2166 번 - 다각형의 면적

백준 2166번 - 다각형의 면적

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	11944	3025	2067	23.451%

문제

2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.

출력

첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

---

예제 입력 1

4
0 0
0 10
10 10
10 0

예제 출력 1

100.0

출처

www.acmicpc.net/problem/2166

2166번: 다각형의 면적

알고리즘 분류

• 기하학
• 다각형의 넓이

접근 방법

다각형의 넓이를 구하는 가장 쉬운 방법은 넓이를 가지는 기본 도형인 삼각형으로 분할하여 각각의 삼각형의 넓이를 모두 더하는 것이다.

즉 과정은 다음과 같다.

 

1. 주어진 다각형을 여러개의 삼각형으로 쪼갠다.
2. 분할 한 삼각형의 넓이를 더한 뒤 합친다.
   1. 삼각형의 세 점의 좌표가 주어졌을 때, 사선 공식(=벡터의 외적)을 통해서 삼각형의 넓이를 구할 수 있다.

 

벡터의 외적을 구현한 알고리즘을 CCW(Counter-Clockwise) 알고리즘이라고 한다.

2021/02/06 - [자료구조 + 알고리즘/기초] - CCW(Counter-Clockwise) 알고리즘

 

단, 2-1 과정에서 외적한 벡터의 방향이 -가 될 수 있으므로, 각각의 삼각형의 넓이는 -가 될 수도 있다는 것을 염두에 두자.

 

예를 들어 다음의 도형이 주어졌다고 생각해보자.

 

다각형을 이루는 순서대로(= 한 획 긋기로) 좌표들이 들어오는데, 1번 좌표를 기준으로 삼아서 나머지 인접한 두개의 꼭짓점의 넓이를 구한다고 했을 때, 더해지는 삼각형의 넓이는 ${\triangle{123}}$ + ${\triangle{341}}$ 이 된다.

이때 ${\triangle{341}}$의 CCW리턴 값은 -가 되므로 자연스럽게 전체 삼각형 ${\triangle{123}}$ - ${\triangle{341}}$의 넓이가 구해진다.

소스 코드

#include <iostream>
#include <vector>

using namespace std;
long long N;
vector<pair<long long,long long>> v;
long long CCW(pair<long long,long long> a, pair<long long,long long> b, pair<long long,long long> c){
    // 벡터의 외적 활용, 곧 CCW가 외적한 결과 벡터가 된다. 방향값을 가짐.
    return (long long)(a.first*b.second)+(b.first*c.second)+(a.second*c.first) -
            (b.first*a.second)-(c.first*b.second)-(a.first*c.second);
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N;
    v.resize(N);

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

    double answer = 0 ;
    for(int i=1; i<N-1; i++){
        answer += CCW(v[0], v[i], v[i+1]) /(double)2;
    }

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

    cout << abs(answer);

    return 0;
}