[백준 2166] 다각형의 면적 (c++)

문제풀이

벡터의 외적을 활용한 문제이다. 

 "다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. "

라는 말을 처음에 파악하지 못해 어려움을 겪었지만

이말인 즉슨 시계방향 혹은 시계반대방향으로 쭉 다각형을 이어 그리며 바로 인접한 점의 점이 주어진다는 것을 의미한다.

 

아마 문제 출제의도였던 CCW라는 알고리즘을 적용하기 좋게 인풋이 주어지도록 한것 같다.

 

CCW는 그냥 내용을 살펴보니 외적을 이용한 사선공식과 같았다. 

 

위의 식이 세점이 주어졌을때 삼각형의 넓이를 구하는 공식이다. 

이를 이용하여 쭉 더하다보면 면적을 구할 수 있다. 

 

이식은 각이 유의미 해서 점의 순서도 중요하다!!

유의해서 문제를 풀면 오목한 다각형의 상황이 나오더라도 예외처리가 된다. (음수의 넓이로 더해지기 때문)

 

 

소스코드

#include <stdio.h>
#include <math.h>
int N;
 
double ccw(double x1, double y1, double x2, double y2, double x3, double y3){
    return (x1*y2+ x2*y3 + x3* y1) - (y1*x2 + y2*x3 + y3*x1);
}
 
double gerAreaOfTriangle(double x1, double y1, double x2, double y2, double x3, double y3){
    return 0.5 * ccw(x1,y1,x2,y2,x3,y3);
}
int main() {
    int N;
    scanf("%d",&N);
    int x[3];
    int y[3];
    
    scanf("%d %d",&x[2], &y[2]);
    int k=0;
    double sum=0;
    scanf("%d %d",&x[k],&y[k]);
    k=(k+1)%2;
    for(int i=2;i<N;i++){
        scanf("%d %d",&x[k],&y[k]);
        sum += gerAreaOfTriangle(x[2],y[2],x[k],y[k],x[(k+1)%2],y[(k+1)%2]);
        k = (k+1)%2;
    }
    
    printf("%.1lf",abs(sum));
    return 0;
}
 

 

문제 링크 : https://www.acmicpc.net/problem/2166

2166번: 다각형의 면적