[백준] 다각형의 면적

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

2166번: 다각형의 면적

우선 문제부터 간단하게 요약하면, 

 

주어진 N개의 점들이 순서대로 이어져 다각형을 구성하게 될 때, 해당 다각형의 넓이를 계산하는 것이 문제입니다. 

 

<Solution>

기본적으로 "삼각형 여러개로 쪼개서 구하는 것이 좋지 않을까" 라는 생각이 가장 처음 듭니다. N각형은 분할된 N-2개의 삼각형의 넓이의 합으로 구할 수 있기 때문입니다. 

 

그러면 이 삼각형의 넓이를 어떤 방식을 이용하여 구하는 것이 가장 효율적일까요?

물론 많은 방법이 있지만, 현재 상황에서 생각 해 볼 수 있는 것들에는 내적, 외적, 헤론의 공식 등의 아이디어가 괜찮아 보입니다.

 

하지만 조금 더 생각해보면, 현재 문제에서 문제조건으로는 

4
0 0
0 10
10 10
10 0

이렇게 딱 정사각형이 예쁘게 나오는 상황을 주었지만, 조금만 바꾸어도 꼬인 도형이 나오는 것을 알 수 있습니다. (self intersecting polygon)

4
0 0
10 10
0 10
10 0

이런 상황또한 고려하기 위해서는 외적이 가장 적합하다는 것을 알 수 있습니다. 

 

따라서 외적을 이용하여 문제를 해결하면 됩니다. 

실제 구현은 아래와 같습니다.

#include <iostream>
#define ld long double

using namespace std;

int N;
struct dot{
    ld x, y;
};

dot dots[10000+10];
ld ldAbs(ld k){
    return (k < 0) ? -k : k;
}

ld crossProduct(dot &d1, dot &d2, dot &d3){ // fixed dot (d2)
    // calculate each component
    ld v1_x = d2.x - d1.x;
    ld v1_y = d2.y - d1.y;
    ld v2_x = d3.x - d2.x;
    ld v2_y = d3.y - d2.y;

    return (v1_x * v2_y - v2_x * v1_y) / 2;
}

ld calArea(){
    ld ret = 0;
    for(int i = 1; i<N-1; i++){
        ret += crossProduct(dots[i], dots[0], dots[i+1]);
    }
    return ldAbs(ret);
}

int main(){
    // getinput
    cin >> N;

    for(int i = 0; i<N; i++){
        cin >> dots[i].x >> dots[i].y;
    }

    cout << fixed;
    cout.precision(1);
    cout << calArea() << endl;
}