백준 2166번 C++ 풀이

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

2166번: 다각형의 면적

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드5

문제

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

입력

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.

출력

첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

예제 입력 1

4
0 0
0 10
10 10
10 0

예제 출력 1

100.0

---

고등학교 때 2차원 직교좌표계에서 임의의 삼각형의 꼭짓점이 모두 주어진 경우 벡터의 외적을 통해 넓이를 바로 구할 수 있는 신발끈 공식을 종종 쓰곤 했는데, 이게 삼각형이 아닌 n다각형에서 쓸수 있다는 것을 처음으로 알게 되었다. 하지만, 선분이 교차해있는 도형에는 쓸 수 없다(https://ko.wikipedia.org/wiki/신발끈_공식).

 

신발끈 공식을 통해 넓이를 구해주자. 다만 출력시 주의해야하는데, cout의 경우 실수형 숫자의 값이 커지게 되면 4e+10과 같은 형식으로 출력된다.

cout << 40000000000.0;

실행결과

4e+10

 

이렇게 출력되면 맞는데도 불구하고 오답이기 때문에, 어쩔수 없이 printf를 통해 출력해주었다. 원래는

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

를 통해 입출력을 빠르게 하는 경우, C언어의 입출력스트림 사용을 지양해야하지만, 별다른 방법도 생각이 안나 어쩔 수 없이 printf를 사용했다.

 

아무튼, 신발끈 공식을 통해 면적을 구하면 된다. 이때 숫자가 int형 범위를 넘어설 수 있기 때문에 long long형으로 처리한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    ll x, y;
    long double S = 0;
    vector<pair<ll, ll>> v;
    
    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> x >> y;
        v.push_back(make_pair(x, y));
    }
    
    for(int i = 0; i < n - 1; i++) {
        S += v[i].first * v[i + 1].second;
        S -= v[i + 1].first * v[i].second;
    }
    S += v[n - 1].first * v[0].second;
    S -= v[0].first * v[n - 1].second;
    S = S < 0 ? -S : S;
    S /= 2;
    printf("%.1Lf", S);
}