BOJ 1708 | 볼록 껍질

기하시러

Convex Hull 알고리즘의 입문 문제다.
볼록 껍질은 주어진 점으로 구성되었지만 점들을 모두 감싸는 다각형을 말한다.

알고리즘 구현 자체는 쉽지만 응용 문제들이 이상한거하고 같이 섞여 나와서 좀 두렵다.

다음과 같은 점들이 주어졌다고 해보자.

먼저 기준점을 잡아야 한다. 기준점은 보통 $x$좌표가 최소인 값이나 $y$좌표가 최소인 값으로 잡는다.

여기서는 $y$좌표가 최소인 값으로 잡겠다.

이제 기준점을 기준으로 나머지 점들을 정렬해보겠다.
기준점과 한 점에 직선을 그어 기준선과 각도가 작을수록 앞에 오도록 정렬한다.

오른쪽부터 반시계방향으로 점들이 정렬된다.
기준점은 0번 인덱스에 있고, 1~N-1번만 정렬해야 한다.
이 부분은 _cmp 함수를 직접 구현해서 사용하자.

이제 전처리가 끝났으니 stack을 하나 만들어서 dot[0]과 dot[1]을 넣고 시작하자.

현재 start = dot[0], middle = dot[1], end = dot[2] 이다.
start->middle 과 middle->end 선분을 CCW 알고리즘을 사용해서 방향 판단을 할 수 있다.

두 직선이 시계방향으로 꺾어지면 음수가 반환되고, 반시계방향으로 꺾어지면 양수가 반환되고, 직선이라면 0이 반환된다.

볼록 껍질은 모든 dot[i] dot[i+1] dot[i+2] 가 반시계방향으로 꺾어진다.

그러므로 위 그림처럼 반시계방향으로 꺾어진다면 stack에 end를 넣고 다음으로 넘어간다.

항상 스택의 dot[top]과 dot[top-1]이 midde과 start로 사용된다. end는 반복문에서 따로 관리하면서 계속 다음 점을 탐색할 수 있도록 한다.

이제 조금 당황스러운 상황에 직면했다.
볼록 껍질을 구성하기 위해서는 4번 점이 아니라 5번 점이 이어져야 하는데 4번 점도 반시계 방향으로 꺾이기 때문에 스택에 들어왔다. 이 문제는 어떻게 해결될까?

바로 다음 점인 5번 점에서 시계 방향으로 꺾이며 이전에 골랐던 점은 문제가 있다는 것을 드러낸다.

이 때 확실하게 잘못된 것은 middle 점이므로 middle 점만을 제거해야 한다.

middle 점은 stack의 top() 에 위치해 있으므로 pop() 연산 한 번으로 제거할 수 있다.

제거한 후에는 3번 점을 middle로 올려서 다시 검사한다.

이렇게 되면 다시 반시계 방향으로 꺾이므로 5를 스택에 넣을 수 있다.

만약 상황이 다음 그림과 같았다면

다시 한번 pop() 되어 middle은 2번이 되고 다시 검사하게 될 것이다.
그래서 도형을 이루는 점은 적절하게 줄어들고, 결국 볼록 껍질을 구성하는 점만 남게 된다.

원래 상황으로 돌아와서, (이제부터는 귀찮으니 색 없이 진행한다.)

이후 과정을 반복하며 마지막에 stack에 들어있는 값이 볼록 껍질을 구성하는 점들의 index가 된다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define ll long long
#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

ll fx, fy;

bool cmp(pair<ll, ll> a, pair<ll, ll> b){
	if (a.second != b.second) return a.second < b.second;
	return a.first < b.first;
}

bool _cmp(pair<ll, ll> a, pair<ll, ll> b){
	ll l = (b.first - fx) * (a.second - fy);
	ll r = (a.first - fx) * (b.second - fy);
	if (l != r) return l < r;
	
	if (a.second != b.second) return a.second < b.second;
	return a.first < b.first;
}

ll ccw(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c){
	return (b.first-a.first)*(c.second-b.second)-(c.first-b.first)*(b.second-a.second);
}

int main(){
	int N; cin >> N;
	vector<pair<ll, ll>> dot;
	for (int i = 0; i < N; i++){
		ll x, y; cin >> x >> y;
		dot.push_back({x, y});
	}
	sort(dot.begin(), dot.end(), cmp);
	fx = dot[0].first; fy = dot[0].second;
	
	sort(dot.begin()+1, dot.end(), _cmp);
	
	//for (auto &i : dot) debug << i.first << ' ' << i.second << endl;
	stack<int> task;
	task.push(0);
	task.push(1);
	
	
	int next = 2;
	while (next < N){
		while (task.size() >= 2){
			ll A, B;
			B = task.top(); task.pop();
			A = task.top();
			
			// if ccw(A, B, next) > 0 => B is edge
			if (ccw(dot[A], dot[B], dot[next]) > 0){
				task.push(B);
				break;
			}
		}
		task.push(next);
		next++;
	}
	
	cout << task.size();
}