백준 No.1708 [볼록 껍질]

BOJ No.1708 [볼록 껍질]

---

  문제 

1708번: 볼록 껍질 (acmicpc.net)

1708번: 볼록 껍질

---

  설명 

 <알고리즘 분류> 
 * 볼록 껍질 / 컨벡스 헐 (Convex hull)

볼록 껍질
  위와 같이 평면 좌표에 N개의 점이 있을 때 점들을 이어 볼록 다각형을 만들면서, 잇지 않은 나머지 점들은 볼록 다각형 내부에 있도록 하는 것 이다.

볼록 껍질을 구현하기 위한 전처리 과정은 아래와 같이 정리할 수 있다.

 

1. 점들 중 껍질을 만들기 시작하는 점을 찾는다.

    - 보통 y값이 제일 작은 점으로 하며, 해당되는 점이 두 개 이상인 경우 해당되는 점들 중 x값이 제일 작은 점으로 한다.

 

2. 시작점을 기준으로 다른 점들을 반시계 방향으로 정렬한다.

-  가장 아래에 있는 점들 중 (y값이 제일 작은 점들 중) 가장 왼쪽에 있는 점 (x값이 제일 작은 점) 을 기준점으로 잡고, 임의의 축을 그려보았다. (하늘색 축)

 

- 주황색 화살표와 같은 순서로 반시계 방향으로 점들을 정렬한다. 각 점 옆에 쓰여져 있는 숫자가 정렬되는 순서이다.

 

 

 

 

 

 

 

3. 반시계 방향으로 정렬을 마친 뒤 스택을 이용하여 컨벡스 홀 알고리즘을 시작한다.

  (-1, 3) 좌표의 점을 시작점으로 가장 끝의 세 점을 순서대로 third, second, first 라 표현하였다. 시작점을 기준으로 반시계 방향으로 정렬이 된 Array 를 순차적으로 접근하면서 진행하면 된다.

 

  다각형에 포함이 되는 점은 Stack 에 쌓이게 된다. 이 때 3, 6번째 같은 상황에 대해 고려를 해야한다. first, second, third 점을 A, B, C 라고 했을 때 아래 두 케이스가 존재한다.

 

 <컨벡스 홀 과정중 고려해야 할 사항> 

 

• First case : A-B 보다 점 C가 우측에 있는경우
• Second case : A, B, C 점들 모두 같은 선상에 있는 경우

 

  위 두 예외 case 를 파악하는 데는 CCW(Counter Clock Wise) 가 사용된다. A, B, C 세 점의 CCW값이 0 이면 세 점은 같은 선 상에 있는 경우이고, 0보다 크면 점 C가 A-B 의 우측에 있는 경우로 파악한다.

참고 사이트 : 2021.06.27 - [Algorithm (C++ based)/Math] - CCW (Counter Clock Wise)​

CCW (Counter Clock Wise)

 

 <정리> 
1. 점들 중 가장 작은 y값을 가지는 점을 시작점으로 한다. (해당되는 점이 여러개인 경우 그 점들 중 가장 작은 x값을 가지는 점을 시작점으로 한다.
2. 시작점을 기준으로 나머지 점들을 반시계방향으로 정렬한다.
3. Stack을 이용하여 컨벡스 헐 알고리즘을 시작한다.
   - 정렬된 Array의 가장 처음 점(시작점) 부터 3개의 점을 Stack에 넣음으로써 시작한다.
   - Stack 에는 볼록 다각형을 형성하는데 필요한 점들이 들어가게 된다.

---

  Code 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#define RIGHT -1
#define LINE 0
#define LEFT 1

using namespace std;

typedef long long LL;

struct point {
	LL x, y;
};

int N;
point sp;
vector<point> arr;
stack<point> s;

LL CCW(point A, point B, point C) {
	LL temp  = (A.x * B.y) + (B.x * C.y) + (C.x * A.y);
	   temp -= (A.x * C.y) + (B.x * A.y) + (C.x * B.y);

	if (temp > 0)	return LEFT;
	else if (!temp) return LINE;
	else			return RIGHT;
}

bool comp1(const point& A, const point& B) { // ORDER BY y ASC, x ASC
	if (A.y != B.y) return A.y < B.y;
	else			return A.x < B.x;
}

bool comp2(const point& A, const point& B) { // 반시계방향으로 정렬
	LL dir = CCW(sp, A, B);
	if (dir)	return dir == LEFT;
	else		return comp1(A, B);
}

int main() {
	cin >> N;

	LL input_x, input_y;
	for (int i = 0; i < N; i++) {
		cin >> input_x >> input_y;
		arr.push_back({ input_x, input_y });
	} 

	sort(arr.begin(), arr.end(), comp1);		// 점들을 y, x 값을 기준으로 오름차순 정렬한다.
	sp = arr[0];								// sp 에 시작점 좌표를 대입한다.
	sort(arr.begin() + 1, arr.end(), comp2);	// 점들을 시작점 기준으로 반시계방향으로 정렬한다.


	// Convex hull 본격적으로 시작!
	point p1, p2, p3;
	p1 = sp;		s.push(p1);				// Stack에 시작점을 넣는다.
	p2 = arr[1];	s.push(p2);				// Stack에 시작점 바로 다음 점을 넣는다.

	for (int i = 2; i < N; i++) {
		p3 = arr[i];						// 현재 점
		
		while (1 < s.size()) {
			p2 = s.top();	s.pop();		// first, second, third 를
			p1 = s.top();					//   정의하기 위해 Stack에서 잠시 뺀다.

			if (CCW(p1, p2, p3) == LEFT) {	// p1, p2, p3 점 세 개로
				s.push(p2);					//   볼록 다각형과 같이 점이 잘 연결 되었다면
				break;						//   Stack에 아까 뺀 두 번째 점을 다시 넣는다.
			}
		}
		s.push(p3);							// third 점을 Stack에 넣는다.
	}

	cout << s.size();
}