다각형의 면적

문제 링크

문제를 푸는 데 필요한 배경지식

1. 두 벡터의 외적

2. cout 소수점 자리수 고정

3. 세 점이 이루는 삼각형의 넓이

점 A, B, C가 이루는 삼각형의 넓이는 AB벡터와 AC벡터의 외적을 통해 구할 수 있습니다.

AB벡터와 AC벡터의 외적의 크기는 AB벡터의 AC벡터를 두 변으로 하는 평행 사변형의 넓이와 같으므로,

외적 크기 / 2를 통해 삼각형의 넓이를 구할 수 있습니다.

문제 풀이

3개 이상의 점들이 다각형을 이루는 순서대로 입력으로 주어집니다.

N개의 점들($P_0...P_{n-1}$)이 이루는 다각형이 볼록 다각형인 경우,

i 번째 점을 입력 받을 때 $\vec{P_0P_{i-1}}\times\vec{P_0P_{i}}$를 계산하여 세 점 $P_0, P_{i-1}, P_{i}$가 이루는 삼각형의 면적을 다 더해주면 다각형의 면적이 됩니다.

만약 N개의 점들이 이루는 다각형이 볼록 다각형이 아닌 경우, 볼록껍질에 포함되지 않는 점이 입력으로 들어왔을 때 $\vec{P_0P_{i-1}}\times\vec{P_0P_{i}}$를 계산해보면, 볼록껍질에 포함되는 점에 대한 외적 결과값과는 부호가 반대가 되는 것을 확인할 수 있습니다.
볼록껍질에 포함되지 않는 점$P_i$가 시작점과 $P_{i-1}$과 이루는 삼각형은 다각형의 면적을 구할 때 더해지는 것이 아니라, -로 빼줘야 다각형의 면적을 구할 수 있습니다.

아래 그림의 경우, 초록색 면적은 더하고, 붉은색 면적을 빼면 전체 다각형의 넓이를 구할 수 있습니다.

위 두가지 경우를 모두 고려하기 위해, 삼각형의 넓이를 구할 때 사용하는 외적의 결과값에 절대값을 취하지 않고, 모두 더한 뒤에, 마지막에만 절대값을 취해주면 답을 구할 수 있습니다.

절대값을 취해야 하는 이유는, 입력이 다각형의 시작점을 기준으로 시계 방향으로 들어올 지, 반시계 방향으로 들어올 지 알 수 없기 때문입니다.

풀이 코드

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

ll n;
double area;

struct Point {
  ll x;
  ll y;
};

double cross_product(Point a, Point b, Point c) {
  return a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y - a.x * c.y;
}

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

  cout.setf(ios::fixed);
  cout.precision(1);

  cin >> n;

  Point start, last, now;
  cin >> start.x >> start.y;
  cin >> last.x >> last.y;

  for(ll i = 2; i < n; i++) {
    cin >> now.x >> now.y;
    area += cross_product(start, last, now) / 2;
    last = now;
  }
  cout << abs(area);

  return 0;
}