백준 2166 - 다각형의 면적

 

 

문제 설명

2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 점이 이루는 도형의 면적을 구하는 것이다.

 

도형은 삼각형이나 사각형과 같이 면적을 구하기 쉬운 도형일 수도 있고 절대 공식으로 구할 수 없는 일그러진 도형일 수도 있다.

해당 문제를 풀기위해 고민하다 그래픽스의 내용이 떠올랐다.

그래픽스에서 도형을 그릴 때 도형을 삼각형으로 나눠 그린다.

즉, 해당 문제도 도형을 삼각형으로 나눠 삼각형의 면적의 합을 구하면 된다고 생각했다.

 

하지만, 실제로 삼각형의 면적을 구하는 법이나 진행방법을 알지는 못했다.

풀이법을 찾아보다 신발끈 공식이라는 것이 있다는 것을 발견했다.

신발끈 공식이란 여러 점을 시계방향 혹은 반시계방향 순서대로 지정하여 다음 공식으로 면적을 구하는 방법이다.

이를 수식화하면 다음과 같다.

$$S = 1/2(x_1y_1+x_2y_3+x_3y_1-x_2y_1-x_3y_2-x_1y_3)$$

따라서, 임의의 한 점을 기준으로 설정하고 다른 두 점과 이루는 삼각형의 넓이를 계속해서 더해나가면 된다.

double GetArea(vector<pair<int, int>>& points)
{
    double result = 0;
    for (int i = 1; i < N - 1; i++) {
        double x1 = points[0].first;
        double y1 = points[0].second;
        
        double x2 = points[i].first;
        double y2 = points[i].second;

        double x3 = points[i + 1].first;
        double y3 = points[i + 1].second;

        double size = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);

        result += size / 2;
    }

    return result;
}

 

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N;

double GetArea(vector<pair<int, int>>& points)
{
    double result = 0;
    for (int i = 1; i < N - 1; i++) {
        double x1 = points[0].first;
        double y1 = points[0].second;
        
        double x2 = points[i].first;
        double y2 = points[i].second;

        double x3 = points[i + 1].first;
        double y3 = points[i + 1].second;

        double size = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);

        result += size / 2;
    }

    return result;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    
    vector<pair<int, int>> points;
    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;

        points.push_back({ a,b });
    }

    double answer = GetArea(points);
    cout << fixed;
    cout.precision(1);
    cout << abs(answer) << endl;

    return 0;
}

---