[C/C++] 백준 #2166 다각형의 면적(벡터)

이번 문제는 기하와 벡터에 대해서 알고 있으면 쉽게 풀 수 있는 문제입니다.  컴퓨터 그래픽 관련해서 자주 쓰이는 기법입니다.

중고등학교 때, 외적(cross product, outer product, vector product)을 배우고 있지만, 실제로 이런데에 쓰일 수 있다는 점들은 잘 모릅니다.

 

문제의 링크는 다음과 같습니다.

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

2166번: 다각형의 면적

 

세점 $O(0,0)$, $A(x_A,y_A)$, $B(x_B,y_B)$가 있다면, 이 세점이 반시계 방향으로 삼각형을 이룰 때, 삼각형의 면적은 다음과 같이 나타낼 수 있습니다.

 

$$S=\frac{1}{2}\overrightarrow{OA}\times \overrightarrow{OB}=\frac{1}{2}(x_A{y}_B-y_A{x}_B)$$

 

외적으로 얻은 벡터의 크기는 두개의 벡터가 이루는 평행사변형의 넓이와 같습니다.  그렇기 때문에 그 값의 $1/2$이 삼각형의 넓이가 됩니다.

 

cross product

평면상에서 두개의 벡터를 외적하면, 해당 평면과 수직인 벡터가 만들어집니다.  해당 평면을 $x-y$ 평면이라고 한다면, 외적을 한 결과는 z값만 나오게 됩니다.  z값 자체가 크기값이므로 이 값을 그대로 절반으로 만들면 됩니다.  저는 일단 절반을 바로 취하지 않고, 나중에 취하는 방식을 했습니다.

 

정수좌표만 주어지므로, 절반을 한다면, 소수점 첫째자리가 0 또는 5인 값만 나오게 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2166 - Polygon's Area
//        - by Aubrey Choi
//        - created at 2019-08-05
//------------------------------------------------
#include <stdio.h>

int main()
{
    int n;
    long long sum=0, x0, y0, xp, yp, x, y;
    scanf("%d%lld%lld", &n, &x0, &y0);
    for(xp=x0, yp=y0; --n;)
    {
        scanf("%lld%lld", &x, &y);
        sum += xp*y - yp*x;
        xp=x, yp=y;
    }
    sum += xp*y0 - yp*x0;
    sum = sum<0?-sum:sum;
    printf("%lld.%lld\n", sum/2, (sum&1)*5);
}