[C++][BOJ] 1708번 볼록 껍질

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

공부 날짜 : 2024.12.20
정답 참조 여부 : X

문제 개요

좌표가 정수인 2차원 점 n개에 대해서
n개을 점을 모두 포함하는 외곽선을 구하며
외곽선 위에있는 점의 개수를 구하는 문제이다.

---

생각 과정

볼록 껍질(Convex Hull)을 구하는 기본적인 문제이다.

가장 먼저 주어진 점들에 대해서 x좌표에 대해 정렬이 필요하다. x좌표를 기준으로 정렬하여 불필요한 비교를 줄이고 왼쪽에서 오른쪽으로 진행하며 꺾이는 방향에 대해 판단 가능하기 때문이다.

이후 꺾이는 방향을 판단하여 볼록껍질을 구하는데 이때 사용하는 방법이 외적(cross product)이다.

두 벡터를 외적했을때 양수이면 반시계방향, 음수이면 시계방향, 0이면 직선임을 판단 할 수 있는데, 결론적으로 위쪽의 볼록껍질은 항상 반시계방향으로 꺾여야 하며, 시계방향으로 꺾이면 그 점은 볼록껍질

아래쪽 기준으로 설명을 하자면

	for (int i = 0; i < N; ++i) {
    	// 볼록껍질을 이루는 점이 2개 이상이며,
        // 마지막 껍질 2개와 새로운 점이 시계방향이라면 
        // 점들을 제거한다( 새로운 점과 연결될때 안쪽으로 생성되는 모든 점 제거
		while (answer > 1 && cross(hull[answer - 2], hull[answer - 1], node[i]) <= 0) {
			--answer;
		}
		// 시계방향으로 꺾이게 되는 점을 제거한 뒤 새로운 점 생성
        // 해당 점이 볼록껍질에 포함되는 점이 아니면 다음 연산 과정에서 제거됨
		hull[answer++] = node[i];
	}

위쪽은 반대로 오른쪽에서 왼쪽으로 탐색하며 반시계 방향으로 꺾이는지 판단하면 된다.

소스코드

#if 1
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

struct Node {
	int x;
	int y;

	bool operator<(const Node& other) {
		if (x == other.x) return y < other.y;
		return x < other.x;
	}

}node[100000];

void merge_sort(int left, int right, Node* arr) {
	if (left >= right) return;

	int mid = (left + right) >> 1;

	merge_sort(left, mid, arr);
	merge_sort(mid + 1, right, arr);

	int i = left;
	int j = mid + 1;
	Node * temp = new Node[right - left + 1];
	int k = 0;

	while (i <= mid && j <= right) {
		if (arr[i] < arr[j]) temp[k++] = arr[i++];
		else temp[k++] = arr[j++];
	}

	while (i <= mid) temp[k++] = arr[i++];
	while (j <= right) temp[k++] = arr[j++];

	for (int i = 0; i < right - left + 1; ++i) arr[left + i] = temp[i];

	delete[] temp;
}

long long cross(const Node& O, const Node& A, const Node& B) {
	return (long long)(A.x - O.x) * (B.y - O.y) - (long long)(A.y - O.y) * (B.x - O.x);
}


int solve() {
	int N;
	std::cin >> N;

	for (int i = 0; i < N; ++i) 
		std::cin >> node[i].x >> node[i].y;

	merge_sort(0, N-1, node);

	Node hull[100000];
	int answer = 0;
	for (int i = 0; i < N; ++i) {
		while (answer > 1 && cross(hull[answer - 2], hull[answer - 1], node[i]) <= 0) {
			--answer;
		}
		hull[answer++] = node[i];
	}

	for (int i = N - 1, t = answer + 1; i >= 0; --i) {
		while (answer >= t && cross(hull[answer - 2], hull[answer - 1], node[i]) <= 0){
			--answer;
		}
		hull[answer++] = node[i];
	}

	return --answer;
}


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

    std::cout << solve() << "\n";
}


#endif