백준 1708 볼록 껍질

볼록 껍질(convex hull) 알고리즘의 기본 문제입니다. 기하는 역시 이것저것 할게 많아서 어려운 것 같습니다 ㅠㅠ..

 

진행 순서는

 

1. y좌표가 가장 작고 그중 x좌표가 가장 작은 점이 나오도록 먼저 정렬을 해서 시작점을 정합니다.

 

2. 0번째 원소를 시작점으로 두고 나머지 N-1개의 점들을 0번째 점과 각도가 작은 순으로 다시 정렬을 합니다.

 

3. 이후 스택에 0,1번째 점을 집어넣고 2번째 점부터 스택의 상위 2개에 있는 점과 CCW를 검사해줍니다.

 

이때 CCW 값이 > 0 이라면 second 점을 포함하고 그렇지 않으면 넣지 않고 진행 해주면 답을 구할 수 있습니다.

 

각도 정렬 조건 함수 같은 경우 두점과 시작점과 CCW를 하여 이 값이 > 0 보다 크면 좌회전을 했다는 의미이므로 시작점과의 각도는 앞에 있는 점이 더 작다는 것을 알 수 있습니다. 따라서 return CCW > 0 과 같이 해주면 되고 만약 세점이 일직선에 있다면 CCW가 0이므로 이경우는 두점중 시작점에 더 가까이 있는 점을 앞으로 두는 방식으로 정렬 하면 됩니다.

 

그림을 그려보고 코드를 보면 이해가 쉬울 것입니다.

 

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

using namespace std;

//Convex hull(볼록 껍질) 연습

struct pos {
	long long x, y;
};

pos v[100010];

bool comp_y(pos a, pos b) {

	if (a.y != b.y)	return a.y < b.y;
	else return a.x < b.x;
}

long long ccw(pos a, pos b, pos c) { //ccw
	return a.x * b.y + b.x * c.y + c.x * a.y - (b.x * a.y + c.x * b.y + a.x * c.y);
}


bool comp_c(pos a, pos b) { //반시계 정렬

	long long cc = ccw(v[0], a, b);
	if (cc != 0) return cc > 0; // 각도 작은 순
	else return (a.x + a.y) < (b.x + b.y); //일직선 있을경우 좌표가 작은
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	stack<pos> s;
	int N; cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> v[i].x >> v[i].y;
	}
		
	sort(v, v + N, comp_y);
	sort(v + 1, v + N, comp_c);		
	
	s.push(v[0]);
	s.push(v[1]);	
	pos first, second;


	for (int i = 2; i < N; i++) {
		while (s.size() >= 2) {
			second = s.top();
			s.pop();
			first = s.top();
			if (ccw(first, second, v[i]) > 0) { //좌회전
				s.push(second);
				break;
			}

		}
		s.push(v[i]);
	}

	cout << s.size();
	return 0;
}