기하

백준 2166 다각형의 면적 문제풀이

[2166 다각형의 면적] https://www.acmicpc.net/problem/2166 .
신발끈 공식을 이용하여 다각형의 면적을 구해보자

문제상황 파악하기.

점들로 구성된 다각형의 넓이를 구하는 문제로 신발끈 공식을 이용하여 구할 수 있다.
점의 최대 좌표는 100000이고 그렇다면 면적을 구할 때 int형을 사용하면 overflow가 나온다.
따라서 면적 구하는 과정에서 long long형을 사용하고 마지막에 나누기 연산을 하고 나서는 double형을 사용하겠다.

아이디어 얻기.

신발끈 공식은 아래 사진과 같다.

이 공식은 오목다각형과 볼록 다각형 모두 성립하므로 사용해도 좋다.

주의할 점

문제는 self-intersect한 다각형에서는 신발끈 공식이 성립하지 않는다는 것이다.
self-intersect인 다각형의 예시는 아래와 같다.
4점 안에서 교차하는 경우인 것이다.
이런경우 다각형이 2개 이상 생겨버려 신발끈 공식을 쓰면 넓이가 상쇄되곤 한다.
알아보니 이 문제는 simple polygon(단순 다각형)만 테스트케이스에 주어지는듯 하다.
찝찝하지만 골드5문제인데 self-intersect까지 쓰기 뭐해서 그냥 제출했다.

나는 틀렸습니다를 하나 받았는데 그 이유는 배열 마지막에 처음 좌표를 넣어두고(계산의 편의를 위함) 그걸 신경쓰지 않고 계산했기 때문이다.

실제 코드

pair를 이용하여 좌표를 나타냈고.
가장 중요한것은 calculateArea 함수의 for문에서 i를 vec 사이즈보다 하나 덜 연산하는 것이다.
왜냐하면 처음에 배열에 마지막원소에 처음원소를 추가했기 때문이다.(신발끈 공식이용의 편의를 위해)

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>

using namespace std;

typedef long long ll;

double calculateArea(vector<pair<ll, ll>> &vec){
    double ret =0;
    for(int i=0;i<vec.size()-1;i++){
        ret += vec[i].first*vec[i+1].second - vec[i+1].first*vec[i].second;
    }
    return abs(ret)/2.0;
}

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    vector<pair<ll, ll>> points(n+1);
    for(int i=0;i<n;i++){
        cin >> points[i].first >> points[i].second;
    }
    points[n].first = points[0].first;
    points[n].second = points[0].second;
    
    cout << fixed;
    cout.precision(1);
    cout << calculateArea(points);
}