백준 문제풀이 : (2166) 다각형의 면적 - C/C++

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

2166번: 다각형의 면적

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	128 MB	Gold 5	기하학 / 다각형의 넓이

 

 

문제

 

 

풀이

다각형의 각 꼭짓점 좌표가 순서대로 주어지기 때문에 첫 번째 점에서 각 점으로 선을 이어 만들어지는 삼각형들의 넓이를 모두 합해주면 된다. 흔히 신발끈 공식이라고 불리는 방법이다.

 

신발끈 공식을 이용하면 일반 다각형과 오목 다각형의 넓이 까지 수월하게 구할 수 있다. 그 원리는 아래 그림과 같다.

 

일반 다각형의 경우, 평범하게 각 꼭짓점의 좌표로 벡터 외적을 계산하며 구한다. 오목 다각형의 경우는 움푹 파이는 부분을 무시하고 일반 다각형이라고 가정하여 넓이를 구한 후, 움푹 파인 영역의 넓이를 감산하면 된다. 

 

하지만 움푹 파인 영역을 이루는 삼각형의 벡터 계산값은 항상 다른 삼각형 영역의 벡터 계산값과 반대되는 부호를 가질 수 밖에 없다. 벡터 계산을 위해 점을 순서대로 조회하기 때문에, 좌표가 움푹 들어간 경우는 삼각형의 세 꼭짓점의 방향이 다른 삼각형들의 반대 방향일 수 밖에 없기 때문이다. 

 

위 그림을 예로 들면, CCW 알고리즘의 규칙에 의해 삼각형ABC의 벡터 외적 값은 점의 궤적이 반시계 방향이기에 양수, 그 외 삼각형들의 벡터 외적 값은 점의 궤적이 시계 방향이기에 음수 결과값이 나온다. 

 

따라서 삼각형들의 모든 벡터 외적 값을 더한 후 해당 값의 절대값을 구하면 움푹 들어간 영역은 자동으로 제외된 결과가 된다.

 

나머지는 코드로 이해하는게 빠르다.

 

 

코드 작성

#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;

typedef double Long;

Long getArea(Long fX, Long fY, Long prevX, Long prevY, int count) {
    
    if (count==0) return 0; 
    
    Long curX, curY;
    scanf("%lf %lf", &curX, &curY);
    
    Long curArea = (prevX-fX)*(curY-fY)-(prevY-fY)*(curX-fX);
    //점이 순서대로 주어지므로, 오목다각형일 경우 점이 그리던 방향이 반대가 됨.
    //이 경우 넓이가 다른 삼각형들과 반대 부호로 계산되어 자동으로 감산된다.
    
    return curArea+getArea(fX, fY, curX, curY, count-1);
    //이번 계산에서 마지막 점으로 사용했던 점이, 다음 계산에서는 두 번째 점이 된다.
}

int main() {
    int T;
    scanf("%d", &T);
    
    Long fx, fy, prevX, prevY;
    scanf("%lf %lf\n%lf %lf", &fx, &fy, &prevX, &prevY);
    //중심이 될 점(fx, fy)과 첫 번째 점(prevX, prevY)를 미리 받아둔다.
    
    double result = getArea(fx, fy, prevX, prevY, T-2)/2*10; 
    //재귀함수에 넘겨준다. 위에서 이미 두 개의 점을 받았으므로, 재귀 반복 횟수는 T-2회가 된다.
    result = (floor(result+0.5))/10;
    //소수점 둘째자리에서 반올림하라고 했으므로, result/2값에 10을 곱한 다음 소수점 첫째자리에서 반올림했다.
    //이후 다시 10으로 나눠주는 작업의 라인이다.
    
    printf("%.1lf", fabs(result));
}

 

 

END.