[백준/C++] 다각형의 면적 (No. 2166)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 말 그대로 다각형의 면적을 계산하는 문제다.

 

최근에 그래픽스를 공부하며 벡터에 대해 공부했기 때문에 쉽게 풀 수 있는 문제였다.

 

다각형의 넓이를 구하기 위해서 아래 그림과 같이 다각형을 분리한다.

 

 

위 그림의 파란색 부분의 넓이를 구하는 방법은 행렬식을 쓰면 된다.

 

1번 점에서 2번 점으로 가는 벡터와, 1번점에서 3번점으로 가는 벡터의 행렬식을 구하면 그 값의 절반이 삼각형의 넓이가 된다.

 

$$ v1 = (x2-x1, \,y2-y1) \;\;\;\; v2 = (x3-x1, \,y3-y1) $$

와 같이 벡터를 구할 수 있으므로, 행렬식을 계산하면

$$ det = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1)$$

으로 파란색 삼각형의 넓이는 det/2가 된다.

(왜냐하면 행렬식은 두 벡터를 이용해 만든 평행사변형의 넓이이기 때문에 삼각형은 2로 나누어주어야 한다.)

이런식으로 다각형을 삼각형으로 전부 쪼개 넓이를 구해 출력하면 된다.

 

 

+ 행렬식이 삼각형의 넓이가 되는 이유를 증명하는 방법도 간단하다.

v1과 v2의 내적으로 cos값을 구할 수 있고, 이를 변환해 sin값을 구하면 넓이와 행렬식이 같음을 알 수 있다.

 

 

​

[아이디어 정리]

1. 다각형을 한 점을 꼭지점으로 하는 삼각형으로 전부 분리한다.
2. 이 때, 삼각형의 넓이는 벡터의 행렬식을 이용해 구할 수 있다.
3. 모든 삼각형의 넓이를 더한 후 절대값을 출력한다.

 

 

Code

 

 

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

double Det(double vx1, double vx2, double vy1, double vy2, double defX, double defY) {
    return (defX-vx1) * (defY-vy2) - (defX-vx2) * (defY-vy1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int N;
    cin >> N;
    long long defX, defY;
    cin >> defX>>defY;
    long long x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    double ans = 0;
    ans += Det(x1, x2, y1, y2, defX, defY)/2;
    for (int i = 3; i < N; i++) {
        x1 = x2, y1 = y2;
        cin >> x2 >> y2;
        ans += Det(x1, x2, y1, y2, defX, defY)/2;
    }
    printf("%.1f", abs(ans));

    return 0;
}

 

---

운 좋게 최근에 공부했던 내용과 관련한 문제라 쉽게 풀 수 있었다.

 

https://www.acmicpc.net/submit/2166/79501195