백준 1708 볼록 껍질

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

1708번: 볼록 껍질

그라함 스캔 알고리즘을 이용해 볼록 껍질 문제를 해결하였습니다.

 

처음 접하는 알고리즘이라 아래 글을 참고하였습니다.

참고 : https://www.crocus.co.kr/1288    

 

볼록 껍질 : Convex hull , 주어진 점들 중 어떤 점을 이어야 모든 내각이 180도 이하가 될 지 구하는 문제입니다.

즉, 껍질처럼 감싸게 되면 주어진 점들로 이루어진 선분은 모두 껍질 안에 포함되게 됩니다.

 

그라함 스캔 알고리즘으로 O(n log n)에 해결이 가능합니다.

 

그라함 스캔 알고리즘

 

1. 전처리 :

1) y좌표, x좌표가 가장 작은 점을 기준점으로 잡는다.

2) 기준점으로부터 반시계 방향으로 다른 점을 정렬한다. (기준점까지의 상대 좌표를 이용)

 

여기서 기준점까지 상대 좌표를 이용해 반시계 방향으로 다른 점을 정렬할 때 외적을 이용합니다.

기준점이 되는 점의 상대 좌표가 (0,0) 일 때, (1,1), (-1,1) 을 반시계 방향으로 잡으면 (1,1), (-1,1) 순임을 쉽게 알 수 있지만, 외적을 이용해 일반화 할 수 있습니다.

상대 좌표의 벡터값이 <1,1>, <-1,1> 이므로 두 벡터를 외적하면 1*1 - (1*(-1)) = 2 > 0 이므로 반시계 방향이 올바름을 알 수 있습니다. 

 

외적 공식 : https://blog.naver.com/mindo1103/90103361104     

간단히 이해하자면, 공간벡터 x, y, z 축 모양으로 생기게 만들면 0보다 큰 값, 반대면 0보다 작은 외적 값을 가집니다.

<1,1> 벡터를 x축으로 생각하고, <-1,1> 벡터를 y축으로 생각하면 z축이 원래 공간좌표의 x,y,z 축과 동일한 모양이므로 외적은 0보다 큽니다.

반대로 <-1,1>, <1,1> 벡터를 외적했다고 치면, <-1,1>을 x축, <1,1>을 y축으로 생각하면 기존 x,y,z 좌표계와 동일한 모양을 가지려면 z축이 뒤집어져야 합니다. 그러므로 이 떄는 외적값이 음수입니다.

 

2. 그라함 스캔 알고리즘

 

기준점을 first, 다음 점을 second 라고 하고, 스택에 넣습니다. 

그리고 다음 점들을 대상으로 ccw 알고리즘을 적용해 좌회전하는지 (외적이 0보다 큰지)를 판단하면 됩니다.

ccw 가 0보다 크다면 다음 점이 second, second가 first 가 되며, 0보다 작다면 그 다음 점을 대상으로 판단합니다.

이를 한 바퀴 돌 때까지 반복하면 됩니다.

 

(우회전 하는 경우면 그 각은 결국 내각이 180도 보다 크게 되는 경로)

 

코드는 다음과 같습니다.

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

using namespace std;

typedef long long ll;

typedef struct info {
	ll x, y; // 실제 위치
	ll p, q; // 기준점으로부터 상대 위치
}info;

int n;
vector<info>dots;
stack<int>st;

void init()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll x, y;
		cin >> x >> y;
		dots.push_back({ x, y, (ll)0, (ll)0 });
	}
}

bool compare_yx(const info& dot1, const info& dot2)
{
	// y좌표, x좌표 작은 순으로 정렬
	if (dot1.y != dot2.y) {
		return dot1.y < dot2.y;
	}
	else {
		return dot1.x < dot2.x;
	}
}

bool compare_counter_clock(const info& dot1, const info& dot2)
{
	// 기준점으로부터 반시계 방향 정렬
	if (dot1.p * dot2.q != dot1.q * dot2.p) { 
		// 기준점 (0,0) 잡았을 때 dot1, dot2 벡터를 외적한 걸로
		// 반시계 방향 판단
		// dot1 x dot2 > 0 => dot1, dot2 순
		// dot1 x dot2 = 0 => 일직선
		// dot1 x dot2 < 0 => dot2, dot1 순
		return dot1.p * dot2.q - dot1.q * dot2.p > 0;
	}
	else { 
		// 일직선인 경우
		// y, x좌표 작은 순으로 
		return compare_yx(dot1, dot2);
	}
}

void sortingDots()
{
	// y좌표, x좌표 순으로 점 정렬
	sort(dots.begin(), dots.end(), compare_yx);

	// 기준점 (0번 점) 으로부터 상대 위치 계산
	ll baseX = dots[0].x;
	ll baseY = dots[0].y; 

	for (int i = 1; i < dots.size(); i++) {
		dots[i].p = dots[i].x - baseX;
		dots[i].q = dots[i].y - baseY;
	}

	// 기준점으로부터 반시계방향 정렬
	vector<info>::iterator iter = dots.begin();
	iter++;
	sort(iter, dots.end(), compare_counter_clock);
}

bool CCW(const info& dot1, const info& dot2, const info& dot3)
{
	// 외적으로 좌회전, 우회전 판단
	// dot1, dot2, dot3 순으로 input
	// dot1 to dot2 vector v1
	// dot2 to dot3 vector v2
	// v1 x v2 > 0 => 좌회전
	// v1 x v2 < 0 => 우회전
	// v1 x v2 = 0 => 직진

	// 그라함 스캔 알고리즘에서는 ccw 좌회전 하는 경우 ( > 0 )
	// 추가 진행하므로 ccw > 0 이면 true

	return dot1.x * dot2.y + dot2.x * dot3.y + dot3.x * dot1.y - (dot1.y * dot2.x + dot2.y * dot3.x + dot3.y * dot1.x) > 0;
}

void graham()
{
	int first = 0;
	int second = 1;
	int next = 2;

	st.push(first);
	st.push(second); // 첫 번째, 두 번째 점 

	while (next < n) { // 점 다 돌 때 까지
		while (st.size() >= 2) { // 다음 점 찾기
			second = st.top();
			st.pop();
			first = st.top();

			// first, second, next ccw > 0 => second 다시 push, break
			// ccw < 0 => 다음 점 찾기

			if (CCW(dots[first], dots[second], dots[next]) == true) {
				st.push(second);
				break;
			}
		}

		// 다음 점 넣기
		st.push(next);
		next++;
	}

	// 최종 볼록 껍질은 스택에 있는 번호 순으로 연결하면 됨
}

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

	init();

	sortingDots();

	graham();

	cout << st.size();
}