백준 2166 c++

문제

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

 

 

 

 

이 문제를 풀려면 ccw 알고리즘에 대해서 알아야한다.

ccw 알고리즘이란?

3개의 점이 있을 때 이 3개의 점을 이은 방향이 시계방향인지 반시계방향인지 직선인지 알려주는 알고리즘이다.

 

다각형의 넓이를 구할 때 사용 되는 이유

 

모든 다각형은 다음과 같이 삼각형으로 나눌 수 있다.

이 삼각형의 넓이를 각각 구한 후 합치면 다각형의 넓이가 되기 때문에 ccw 알고리즘을 통해서 삼각형의 넓이를 구한 후 하나로 합쳐주게 되면 다각형의 넓이를 구할 수 있게 된다. 

 

+

이 때 조금 특별한 점은 

 

다음과 같이 다각형이 오목하게 들어가는 부분에서 발생한다. 

ccw 알고리즘을 동작하면 오목하게 들어간 부분은 반시계방향으로 -값이 return 된다. 따라서 오목한값도 그대로 ccw알고리즘의 리턴값들을 더해주면 다각형의 면적을 구할 수 있다.

 

 

 

3개의 꼭지점 좌표를 가진  삼각형의 넓이를 구하는 공식 - 신발끈 공식

아래의 ccw함수가 이런 신발끈 공식을 그대로 사용하는 것을 볼 수 있다. (x1,y1),(x2,y2),(x3,y3) 이 3개의 꼭지점 좌표를 각각 신발끈 모양으로 엮어서 곱해주고 빼준 후 나누기 2를 해주면 삼각형의 넓이를 구할 수 있다.

 

 

#include<iostream>
#include<vector>
#include<math.h>
#include<bits/stdc++.h>

using namespace std;
typedef pair<double, double>P;

double ccw(double x1, double x2, double x3, double y1, double y2, double y3) {
    double res = x1 * y2 + x2 * y3 + x3 * y1;
    res += (-y1 * x2 - y2 * x3 - y3 * x1);
    return res / 2;
}

int main() {
    int n; cin >> n;
    vector<P>arr(n);

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

    double res = 0;
    for (int i = 2; i < n; i++)
        res += ccw(arr[0].first, arr[i - 1].first, arr[i].first, arr[0].second, arr[i - 1].second, arr[i].second);

    cout.setf(ios::fixed);
    cout.precision(1);

    cout << abs(res);

    return 0;
}

 

 

 

참고 

https://snowfleur.tistory.com/98 

https://cocoon1787.tistory.com/486

https://ip99202.github.io/posts/%EB%B0%B1%EC%A4%80-2166-%EB%8B%A4%EA%B0%81%ED%98%95%EC%9D%98-%EB%A9%B4%EC%A0%81/

[C/C++] 백준 2166번 - 다각형의 면적 (신발끈 공식)

[알고리즘] CCW(Counter Clock Wise)