[C++]백준 1708 - 볼록 껍질

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

1708번: 볼록 껍질

 

 

 

 

 

 

Convex Hull

문제에선 Convex Hull에 대한 설명을 하는데 Convex Hull이란

가장 바깥쪽에 있는 정점들을 이어서 만드는 볼록 다각형을 뜻한다.

이런 Convex Hull을 만드는 알고리즘 중에서는 Graham's Scan 알고리즘이 있다.

 

이 문제는 Graham's Scan 알고리즘으로 풀었는데 이 알고리즘에 대해 설명하자면먼제 Convex Hull을 자세히보면 이어진 정점들이 모두 시계방향 혹은 반시계 방향으로이어져 있는것을 볼 수 있다.이러한 특성을 통해서 Convex Hull 정점들을 쉽게 찾을 수 있다.

 

다음은 Convex Hull 정점들을 찾는 순서다.

 

1. 가장 Y값이 가장 작은 기준점을 선택한다.만약 Y값이 가장 작은것이 여러개가 있다면 X값이 작은걸로 한다.

 

2. CCW를 통해서 기준점에 대해 정점들을 반시계 방향으로 정렬한다.

 

3. 정렬된 노드들을 순회하면서 현재 정점에서 다음 정점이 좌측에 있는 노드만 연결한다.

 

 

그림으로 살펴보자 먼저 기준점인 가장 아래쪽에 있는 정점을 선택한다.

그리고 CCW를 이용해 기준점으로 부터 반시계 방향으로 정렬한다.

이제 스택을 이용해서 정렬된 노드를 순회하면서 정점이 좌측에 존재하는지 확인하면 된다.

먼저 첫번째로 0,1,2 정점을 확인 하는데 순서대로 스택에 넣고

2번 정점이 0과 1을 이은 선분 왼쪽에 있기 때문에 넘어간다.

다음 3번 노드도 1과 2번 정점을 이은 선분의 왼쪽에 있으므로 스택에 추가한다.

4번노드는 2,3번 선분의 좌측이 아닌 우측에 있는데 이때는 스택의 맨 위에 있는 3번을 제거하고 4번을 추가한다.

그러면 이러한 모습이 된다.

5번은 좌측에 있느니 추가.

하지만 6번이 우측에 있기때문에 스택의 맨 위인 5를 제거하고 6을 추가

그리고 마지막으로 7번을 추가함으로써 Convex Hull이 완성된다.

풀이

---

개인적으로 많이 헷갈린 부분이 정점 정렬쪽이였다.

정렬은 2번을 해야했는데 첫번째 정렬은 y가 낮은 순으로 y가 같다면 x가 낮은게 더 앞에오게 하고

두번째 정렬은 CCW를 이용해 왼쪽에 있을경우 만약 CCW가 0이라면 거리가 더 가까운 것이 앞에오게 정렬해야한다.

코드

---

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;

long long point[100005][2];
int N;
vector<int> sortList;

long long Cross(int x1, int y1, int x2, int y2) {
	return (long long)x1 * y2 - (long long)x2 * y1;
}
long long CCW(int p1, int p2, int p3) {
	int x1 = point[p2][0] - point[p1][0];
	int x2 = point[p3][0] - point[p1][0];
	int y1 = point[p2][1] - point[p1][1];
	int y2 = point[p3][1] - point[p1][1];
	return Cross(x1, y1, x2, y2);
}

long long dist(int x1, int y1, int x2, int y2) {
	long long x = (long long)x2 - x1;
	long long y = (long long)y2 - y1;
	long long d = sqrt(x * x + y * y);
	return d;
}
bool compare(int a, int b) {
	int x1 = point[a][0];
	int y1 = point[a][1];
	int x2 = point[b][0];
	int y2 = point[b][1];

	if (y1 == y2) {
		return x1 < x2;
	}
	else {
		return y1 < y2;
	}
}
bool compare2(int a, int b) {
	int x0 = point[sortList[0]][0];
	int y0 = point[sortList[0]][1];
	int x1 = point[a][0];
	int y1 = point[a][1];
	int x2 = point[b][0];
	int y2 = point[b][1];

	long long ccw = CCW(sortList[0], a, b);
	if (ccw == 0) {
		return dist(x0, y0, x1, y1) < dist(x0, y0, x2, y2);
	}
	return ccw > 0;
}
int main() {
	cin >> N;

	int minY = 1000000;
	int minX = 1000000;
	int minYIndex = 0;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		point[i][0] = x;
		point[i][1] = y;
		if (y <= minY && x <= minX) {
			minY = y;
			minX = x;
			minYIndex = i;
		}
	}
	sortList.push_back(minYIndex);
	for (int i = 0; i < N; i++) {
		if (i == minYIndex)
			continue;
		sortList.push_back(i);
	}
	sort(sortList.begin(), sortList.end(), compare);
	sort(sortList.begin() + 1, sortList.end(), compare2);
	for (int index = 0; index < sortList.size(); index++) {
		int prev = index - 1 < 0 ? sortList.size() - 1 : index - 1;
		int next = index + 1 > sortList.size() - 1 ? 0 : index + 1;
		long long ccw = CCW(sortList[prev], sortList[index], sortList[next]);

		if (ccw <= 0) {
			sortList.erase(sortList.begin() + index);
			index -= 2;
		}
	}
	cout << sortList.size();
}