[BOJ] 2166 - 다각형의 면적

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

BOJ - 다각형의 면적

문제 유형: 수학, 선형대수, 기하학

문제 난이도: Gold V

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

 

입력

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

 

출력

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

 

풀이

볼록 또는 오목다각형에서 순서대로 N개의 점의 좌표가 주어진다면, 신발끈 공식을 이용해서 다각형의 넓이를 구할 수 있다.

 

두 벡터의 외적은 두 벡터가 이루는 평행사변형의 넓이를 나타낸다.

그의 절반은 한 점에서 출발한 두 벡터를 기준으로 만들어지는 삼각형의 넓이가 된다.

 

다각형 안의 임의의 점을 찍고, 그 점을 기준으로 다각형을 여러 삼각형으로 분해한다고 해보자.

이 삼각형의 넓이를 계산하여 합치면 전체 다각형의 넓이가 구해진다.

삼각형을 일관된 꼭짓점 순서로 계산하여, 벡터 외적으로 계산하면 

가 된다.

단, 조건은 주어진 입력의 좌표들이 순차적으로 그려지는 형태여야 한다는 것이고, 여기서는 이를 만족한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  int n;
  cin >> n;
  vector<pair<double, double>> points(n);
  for (int i = 0; i < n; ++i) {
    cin >> points[i].first >> points[i].second;
  }

  double a = 0, b = 0;
  for (int i = 0; i < n; ++i) {
    int j = (i + 1 + n) % n;
    a += (points[i].first * points[j].second);
    b += (points[j].first * points[i].second);
  }

  double ans = abs(a - b) / 2;

  cout << fixed << setprecision(1) << ans << "\n";

  return 0;
}