baekjoon 2166:다각형의 면적

baekjoon 2166 다각형의 면적

2166번 다각형의 면적

접근

매번 절댓값해서 더해야하는 줄 알았는데 그러면 오목다각형을 계산하지 못한다고 한다. 신발끈 공식을 이용하는 것처럼 그냥 음수도 처음엔 절댓값 붙이지 않고 더해줘야
오목다각형의 경우 서로 상쇄되는 효과가 나서 정확한 넓이를 구할 수 있다.
마지막에 절댓값해주면 된다.

코드

//2166
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
long long int sizeCal(pair<long long int, long long int> a, pair<long long int, long long int> b, pair<long long int, long long int> c){
  pair<long long int, long long int> v1 = {b.first - a.first, b.second - a.second};
  pair<long long int, long long int> v2 = {c.first - a.first, c.second - a.second};
  // cout << v1.first * v2.second - v1.second * v2.first << "\n";
  return v1.first * v2.second - v1.second * v2.first;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  vector<pair<long long int, long long int>> v(n);
  for(int i = 0; i < n; i++){
    long long int a, b;
    cin >> a >> b;
    v[i] = {a, b};
  }
  // for(auto i : v){
  //   cout << i.first << ' ' << i.second << '\n';
  // }
  long long int ans = 0;
  for(int i = 0; i <= n-3; i++){
    ans += sizeCal(v[0], v[i+1], v[i+2]);
  }
  double anss = (double)ans/2;
  cout << fixed << setprecision(1) << abs(anss);
  
  
  return 0;
}

배운 점

union-find에 대해 응용도 해보았고, union-find가 분리 집합을 만드는 알고리즘 중 하나라는 것을 알게 되었다.
union-find의 구현도 여러가지 방법이 있다는 것을 알게 되었다.