볼록 껍질 알고리즘 (Convex Hull Algorithm)

Monotone chain, a.k.a. Andrew's algorithm— $O(n log n)$
Published in 1979 by A. M. Andrew. The algorithm can be seen as a variant of Graham scan which sorts the points lexicographically by their coordinates. When the input is already sorted, the algorithm takes $O(n)$ time.
-https://en.wikipedia.org/wiki/Convex_hull_algorithms

모노톤 체인

위 껍질과 아래 껍질을 따로 구해서 합치는 알고리즘.

0. 점들을 $x$좌표, $y$좌표 순으로 정렬 $O(n log n)$

위 껍질 구하기

1. 순서대로 점들을 탐색
2. 스택의 크기가 2보다 크고 스택의 위의 2개의 점과 현재 탐색 중인 점이 $CW$가 아닐 때까지 $pop$
3. 현재 탐색 중인 점을 $push$
4. 스택에 있는 점들이 위 껍질을 이룸.

아래 껍질 구하기

5. 위 껍질 구하는 과정에서 $CW$를 $CCW$로 바꾸어 아래 껍질을 구할 수 있음.

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

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define fi(n, m) for (int i = n; i < m; i++)
#define fj(n, m) for (int j = n; j < m; j++)
#define fk(n, m) for (int k = n; k < m; k++)

ll clockwise(const pii& a, const pii& b, const pii& c) {
  ll vx, vy, wx, wy;
  vx = a.first - b.first;
  vy = a.second - b.second;
  wx = b.first - c.first;
  wy = b.second - c.second;
  return (vx * wy - vy * wx);
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vpii arr(n);
  fi(0, n) cin >> arr[i].first >> arr[i].second;
  
  // 0. 점들을 x좌료, y좌표 순으로 정렬
  sort(arr.begin(), arr.end());
  vpii shell, shell2; // shell: 위 껍질 스택, shell2: 아래 껍질 스택
  int size2 = 0, size = 0; // size: 위 껍질 스택 크기, size2: 아래 껍질 스택 크기
  
  // 1. 순서대로 점들을 탐색하며
  fi(0, n) {
  
  	// 위 껍질 
  	// 2. 스택의 크기가 2보다 크고 스택의 위의 2개의 점과 현재 보고 있는 점이 CW가 아닐 때까지 pop
    while (size >= 2 &&
           clockwise(shell[size - 2], shell[size - 1], arr[i]) >= 0) {
      shell.pop_back();
      size--;
    }
    // 3. 현재 탐색 중인 점을 push
    shell.push_back(arr[i]);
    size++;
    
    // 아래 껍질
    // 2. 스택의 크기가 2보다 크고 스택의 위의 2개의 점과 현재 보고 있는 점이 CCW가 아닐 때까지 pop
    while (size2 >= 2 &&
           clockwise(shell2[size2 - 2], shell2[size2 - 1], arr[i]) <= 0) {
      shell2.pop_back();
      size2--;
    }
    // 3. 현재 탐색 중인 점을 push
    shell2.push_back(arr[i]);
    size2++;
  }
  /* 위 껍질과 아래 껍질은 x좌표가 최소인 점과 최대인 점을 공유하므로
  	위 껍질 스택 크기와 아래 껍질 스택 크기의 합에서 에서 2를 빼서
    볼록 껍질 점의 개수를 구해줌 */
  cout << size + size2 - 2 << '\n';
}