[ 백준 ] 2166 / 다각형의 면적

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
197/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 2166 / 다각형의 면적
 *
 * Kind :: Math
 *
 * Insight
 * - u 와 v 라는 3차원 벡터의 외적은 다음과 같다
 *   u = (u1, u2, u3), v = (v1, v2, v3)
 *   + u x v = (u2*v3 - u3*v2, u3*v1 - u1*v3, u1*v2 - u2*v1)
 *     # u 와 v 가 u3=0, v3=0 인 2차원 벡터라면 외적은 다음과 같다
 *       u x v = (0, 0, u1*v2 - u2*v1)
 *       -> D = u1*v2 - u2*v1 이라고 하면
 *          바로 이 D 의 절댓값이 u 와 v 로 이루어진 평행사변형의 넓이다
 *          따라서, u 와 v 로 이루어진 삼각형의 넓이는 D 의 절댓값을 2로 나누어주면 구할 수 있다
 *
 * - 위의 D 는 방향을 가지는 벡터이다
 *   방향 없이 물리량만을 가지고 있는 스칼라와는 달리
 *   방향에 따라서 값을 더하거나 빼주어야 한다
 *   + 볼록다각형의 경우 임의의 한 점을 중심으로
 *     시계 방향(또는 반시계 방향)으로 다각형의 넓이를 구한다고 하자
 *     각 점이 시계 방향(또는 반시계 방향)순서대로 A, B, C, ..., Z 라고 하면
 *     볼록다각형의 넓이 = 삼각형 A B C 의 넓이
 *                       + 삼각형 A C D 의 넓이
 *                       + ...
 *                       + 삼각형 A Y Z 의 넓이
 *     # 각 삼각형의 CCW 의 값 D 모두 시계 방향(또는 반시계 방향) 이므로
 *       D 의 값을 모두 더한 후 절댓값으로 만들어주고 2로 나누어주면
 *       이 값이 바로 볼록다각형의 넓이가 된다
 *   + 오목다각형의 경우도 마찬가지로 임의의 한 점을 중심으로
 *     시계 방향(또는 반시계 방향)으로 다각형의 넓이를 구한다
 *     각 점이 시계 방향(또는 반시계 방향)순서대로 A, B, C, ..., Z 라고 하면
 *     볼록다각형과 마찬가지로 오목다각형의 넓이 = 삼각형 A B C 의 넓이
 *                                            + ...
 *                                            + 삼각형 A Y Z 의 넓이 이지만
 *     # 각 삼각형의 CCW 의 값 D 의 방향이 반대일 수 있다!
 *       볼록한 부분과 오목한 부분이 있기 때문이다
 *       이 때 각 삼각형의 CCW 의 값 D 에서 방향이 반대이므로 부호도 서로 반대이다
 *       -> 중요한 점은 이 D 를 절댓값을 취하지 않고 더해야한다는 것이다
 *          볼록한 부분이 넓이로써 더해지는 부분이라면
 *          오목한 부분은 넓이로써 빼주어야 하는 부분이기 때문이다
 *
 * Point
 * - 요약 : 외적은 방향을 가진다
 *   + 볼록한 부분은 더해주고 오목한 부분은 빼주어야 하므로
 *     # 삼각형을 이루는 벡터들의 외적한 값 D 의 부호를 그대로 유지시킨 채 더해주어야
 *       넓이를 올바르게 구할 수 있다
 *
 * - 좌표계산시 int 일 경우 Overflow 가 일어날 수 있으므로
 *   long 을 써주도록 하자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cmath>

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Point { long x, y; };

// Set up : Functions Declaration
Point getVector(Point s, Point e);
long getCross(Point v1, Point v2);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    Point P[N];
    for (int i=0; i<N; i++)
        cin >> P[i].x >> P[i].y;

    // Process
    long size = 0;
    Point s = P[0]; /* 임의의 한 점 고정 <= A */
    for (int i=1; i<N-1; i++) {
        /* 삼각형을 이루는 점의 순서는 시계방향(또는 반시계방향)으로 주어져야 함 
         * ^= 문제에서 다각형을 이루는 순서대로 점이 주어짐 */
        Point e1 = P[i]; /* 삼각형을 이루는 나머지 점 <= B, C, D, ... */
        Point e2 = P[i+1]; /* 삼각형을 이루는 나머지 점 <= C, D, E, ... */
        Point v1 = getVector(s, e1); /* v1 = Vector(Point s -> Point e1) */
        Point v2 = getVector(s, e2); /* v2 = Vector(Point s -> Point e2) */
        long D = getCross(v1, v2); /* v1 x v2 */
        size += D;
    }

    // Control : Output
    cout << fixed;
    cout.precision(1);
    cout << fabs(size / 2.0) << endl;
}

// Helper Functions
Point getVector(Point s, Point e)
/* 점 s 로부터 점 e 까지의 벡터를 반환 */
{
    return {e.x - s.x, e.y - s.y};
}

long getCross(Point v1, Point v2)
/* 이차원 벡터 v1 과 v2 의 외적의 값을 반환 */
{
    return v1.x * v2.y - v1.y * v2.x;
}
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글