취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1708번 문제인 볼록 껍질이다.
문제는 아래 링크를 확인하자.

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

주어진 점들의 convex hull을 이루는 점의 개수를 구하는 문제이다. convex hull을 구해 그 점의 개수를 세는 것으로 문제를 해결하자.

convex hull을 구하는 알고리즘은 크게 Graham scan과 Andrew's algorithm (Monotone chain algorithm) 두 가지가 잘 알려져있다. 이와 같은 convex hull을 구해내는 알고리즘 중 하나를 이용해 문제를 해결하자. 글쓴이의 코드는 Andrew's algorithm을 이용하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int N;
pair<ll, ll> points[100000]; // 입력받기
vector<pair<ll, ll>> upperhull;
vector<pair<ll, ll>> lowerhull;

int CCW(pair<ll, ll>& A, pair<ll, ll>& B, pair<ll, ll>& C) {
	ll ccw = (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
	if (ccw > 0) return 1;
	else if (ccw < 0) return -1;
	else return 0;
}

void andrew_algorithm() {
	sort(points, points + N);
	
	//upperhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = upperhull.size();
		while (cursize > 1) {
			auto& L = upperhull[cursize - 2], & M = upperhull[cursize - 1];
			if (CCW(L, M, cur) != -1) upperhull.pop_back(), cursize--;
			else break;
		}
		upperhull.emplace_back(cur);
	}

	//lowerhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = lowerhull.size();
		while (cursize > 1) {
			auto& L = lowerhull[cursize - 2], & M = lowerhull[cursize - 1];
			if (CCW(L, M, cur) != 1) lowerhull.pop_back(), cursize--;
			else break;
		}
		lowerhull.emplace_back(cur);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> points[i].first >> points[i].second;
	
	andrew_algorithm();

	cout << upperhull.size() + lowerhull.size() - 2;
}