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

메르센고수·2023년 8월 10일

cpp 수학

Baekjoon

목록 보기

11/48

문제 - 다각형의 면적 (Gold5)

[백준 2166]

참고

* CCW

위의 관계를 보면 알겠지만, CCW를 시계방향으로 구하면 음수값이 출력되기 때문에 이 문제에서는 면적을 구하기 위해 절댓값을 취해줘야 한다.

* 외적

위의 식을 통해 구하면 또 하나의 벡터가 구해지는데, 그 벡터의 크기가 곧 a,b 벡터로 구성되는 평행사변형의 면적이 된다.

풀이 전략

벡터의 외적의 크기가 평행사변형의 넓이 임을 이용한다.

원점과 다른 두 점 사이의 CCW 공식
: (a,b,c), (d,e,f) 일 때

CCW=(ae+bf+cd)-(bd+ce+af)=ae-bd

입력하는 점의 순서가 반시계 방향이면 값이 양수로 출력되고, 시계방향이면 값이 음수로 출력되기 때문에 결과값에 abs함수를 씌워서 절댓값으로 출력한다.

CCW 공식을 사용하면 평행사변형들을 더한 결과가 출력되기 때문에 1/2를 곱해줘야 큰 삼각형들에서 작은 삼각형들을 빼준 면적이 나와서 구하고자 하는 면적을 구할 수 있게 된다.

소스 코드

#include <iostream>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;

    long x[100000],y[100000];

    for(int i=0;i<N;i++){
        cin>>x[i]>>y[i];
    }
    x[N]=x[0];
    y[N]=y[0];
    // CCW 공식을 사용하기 위해 처음 좌표를 마지막에 복사
    double result=0;

    for(int i=0;i<=N;i++){
        result+=((x[i]*y[i+1])-(x[i+1]*y[i]));
    } // CCW 공식
    cout<<fixed;    
    cout.precision(1); // 소수점 1자리까지 출력
    cout<<abs(result)/2.0<<endl; // 결과값에 절댓값을 취한 뒤 1/2배
    return 0;
}