백준 2166번 [다각형의 면적](C++) -yes6686- 티스토리

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

---

문제 링크: https://www.acmicpc.net/problem/2166

문제 설명:

N개의 꼭짓점을 가진 다각형의 좌표가 주어졌을 때, 다각형의 면적을 계산하는 문제입니다. 좌표는 시계 방향 또는 반시계 방향으로 주어지며, 다각형은 자기 교차하지 않습니다.

---

문제 해결 코드

#include <iostream>
#include <cmath>
using namespace std;

double x[10001];
double y[10001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    long double sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    // 면적 계산 (신발끈 정리)
    for (int i = 1; i <= n; i++) {
        sum += x[i] * y[i % n + 1];
        sum -= y[i] * x[i % n + 1];
    }

    cout << fixed;
    cout.precision(1);
    cout << abs(sum) / 2.0 << '\n'; // 절댓값을 취하고 면적 계산
}

예제

입력:
4
0 0
0 10
10 10
10 0

출력:
100.0

---

코드 설명

• 신발끈 정리: 다각형의 면적을 계산하는 공식으로, 점들의 좌표를 이용해 시계 방향 또는 반시계 방향으로 면적을 구합니다.
• 좌표 입력: x와 y 배열에 각각 좌표를 저장합니다.
• 면적 계산: 모든 점을 순회하며 x[i]*y[i+1] - y[i]*x[i+1]를 누적 계산합니다. 마지막 점은 첫 번째 점과 연결하여 처리합니다.
• 결과 출력: 누적된 값의 절댓값을 취하고 2로 나누어 면적을 구합니다. 소수점 1자리까지 출력합니다.

시간 복잡도

• 점의 개수 N에 대해 O(N)으로, 모든 점을 순회하며 면적을 계산합니다.

---

결과

이 코드는 신발끈 정리를 활용하여 다각형의 면적을 정확히 계산합니다. 입력으로 주어진 좌표에 따라 다각형의 넓이를 올바르게 구할 수 있습니다.