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

[문제]

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

2166번: 다각형의 면적

---

[문제 풀이]

신발끈 공식을 알면 비교적 쉽게 풀 수가 있던 문제였다.

다각형의 넓이를 구하는 방법은 삼각형을 만든 뒤에 해당 삼각형의 넓이를 모두 더하면 해당 넓이가 된다는 것을 우리들은 배웠다.

사각형의 경우는 삼각형 2개를 합쳐서 만들어진것이고 오각형의 경우에는 삼각형 3개가 합쳐진 경우이다.

즉, 해당 다각형을 구하기 위해서는 꼭지점 1개를 모두 공유하는 삼각형들의 모든 넓이를 더하면 된다.

 

하지만, 단순히 x와 y좌표만을 주고 삼각형 넓이를 모두 구하자니 계산이 너무 어려워진다.

그러니, 신발끈 공식을 이용해서 풀어보자.

https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D

신발끈 공식 - 위키백과, 우리 모두의 백과사전

해당 공식을 이용하면 삼각형의 넓이는 

로 계산이 된다.

이제 해당 공식을 이용해서 풀어보도록 하자.

---

[코드]

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

double solve(vector<double> x, vector<double> y, int n){
    double answer = 0.0;
    for(int i = 2;i<n;i++){
        answer += x[0] * y[i-1] + x[i-1] * y[i] + x[i] * y[0];
        answer -= x[i-1] * y[0] + x[i] * y[i-1] + x[0] * y[i];
    }
    return answer;
}

int main(){
    int n;
    cin>>n;
    vector<double> x(n,0);
    vector<double> y(n,0);
    for(int i = 0;i<n;i++){
        cin>>x[i];
        cin>>y[i];
    }
    double answer = solve(x,y,n) / 2;
    cout<<fixed;
    cout.precision(1);
    cout<<abs(answer)<<endl;
    return 0;
}