[BOJ 2254] 감옥 건설

풀이

convex hull이라는 생소한 알고리즘을 사용해서 푸는 문제였다. 거의 접해보지 못한 문제 유형이기 때문에 공부할 겸 풀이를 참고하여 문제를 풀었다.

convex hull 알고리즘만 알면 사고 과정을 간단하다.

1. convex hull 알고리즘을 이용하여 볼록껍질을 찾는다.
2. 감옥좌표가 위에서 찾은 볼록껍질 안에 들어있는지 확인한다.
   2-1. 볼록껍질 모든 좌표와 감옥 좌표의 CCW를 계산하여 다른 방향이 있는지 확인하면 볼록껍질 내부에 감옥이 있는지 확인할 수 있음
   2-2. 감옥좌표에서 한 방향으로 직선을 그었을 때 홀수개의 교점이 생기면 내부에 있고 짝수개의 교점이 생기면 외부에 있다고 판단할 수 있음
3. 위 두 방법 중 하나를 이용하여 감옥 좌표가 내부에 있으면 위에서 찾은 볼록껍질 좌표들은 제거하고 다시 1번으로 돌아간다. 만약 내부에 존재하지 않으면 나머지 좌표들도 감옥을 포함하지 못하므로 정답 출력 후 종료한다.

더 공부해야할 것들

• ccw
• convex hull에서 상대좌표를 구해서 정렬하는 이유

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

struct info {
	long long x, y, p, q;
	info(int x = 0, int y = 0) : x(x), y(y), p(1), q(0) {}
};
int n;
pair<int, int> target;
vector<info> arr;

bool cmp(info& a, info& b) {
	if (a.q * b.p != a.p * b.q) return a.q * b.p < a.p * b.q;
	if (a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}

long long ccw(info& a, info& b, info& c) {
	long long t = a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y - a.x * c.y;
	if (t > 0) return 1;
	else if (t == 0) return 0;
	else return -1;
}

bool isInside(pair<int, int>& target, stack<int> S) {
	int first = S.top(); S.pop();
	int start = first;
	int second = S.top(); S.pop();
	info P(target.first, target.second);
	int direct = ccw(arr[first], arr[second], P);
	while (!S.empty()){
		first = second;
		second = S.top();
		S.pop();
		if (direct != ccw(arr[first], arr[second], P)) return false;
	}
	if (direct != ccw(arr[second], arr[start], P)) return false;
	return true;
}


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

	cin >> n >> target.first >> target.second;
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		arr.push_back(info(a, b));
	}
	int ans = 0;


	while (arr.size() >= 3) {
		sort(arr.begin(), arr.end(), cmp);
		for (int i = 1; i < arr.size(); i++) {
			arr[i].p = arr[i].x - arr[0].x;
			arr[i].q = arr[i].y - arr[0].y;
		}
		sort(arr.begin() + 1, arr.end(), cmp);

		stack<int> S;
		S.push(0);
		S.push(1);

		int next = 2;

		while (next < arr.size()) {
			while (S.size() >= 2) {
				int second = S.top();
				S.pop();
				int first = S.top();

				// 좌회전(ccw > 0)이면 second push 아니면 계속 진행
				if (ccw(arr[first], arr[second], arr[next]) > 0) {
					S.push(second);
					break;
				}
			}
			S.push(next++);
		}
		if (!isInside(target, S)) break;
		ans++;
		while (!S.empty()) {
			for (auto iter = arr.begin(); iter != arr.end();) {
				if (iter->x == arr[S.top()].x && iter->y == arr[S.top()].y) {
					iter = arr.erase(iter);
					break;
				}
				else iter++;
			}
			S.pop();
		}
	}
	cout << ans;

	return 0;
}