[PS] 백준 #1708. 볼록 껍질

문제 정보

• 난이도: 플래티넘 V
• 문제 주소: https://www.acmicpc.net/problem/1708
• 이 문제를 푼 이유: 300번째 문제 기념

 

문제

다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.

조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.

점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을 작성하시오.

 

나의 풀이

백준 300번째 문제로 의미 있는 문제를 풀고 싶어서 어떤걸 풀까 고민하다가 마침 저번 학기 알고리즘 시간에 배운 Convex Hull 알고리즘이 떠올랐고 난이도도 꽤 어려워서 이 문제를 선정하게 되었다. Graham Scan 알고리즘을 사용해야 한다는 건 수업 때 공부했기 때문에 이걸 그대로 구현만 하였다. (https://pongkijoa.tistory.com/17 참고) 

1. 시작점 찾기: 먼저 각 좌표들을 입력한 뒤에 가장 좌하단에 있는 점을 찾아서 시작점으로 정한다. comp 함수를 통해 점들을 정렬해서 시작점을 찾았다.

2. 각도순 정렬: 시작점과 나머지 점들간의 각도들 (라디안 단위)을 구해서 degrees 배열에 저장한다. x좌표가 같을 경우 pi/2, y좌표가 같을 경우 0 (왼쪽은 없다), 그 외에는 기울기의 arctan 값을 구했다. arctan 함수는 음수도 나오기 때문에 대칭이동을 통해서 pi + degree 로 바꿔서 사용했다. 이제 각 점들의 좌표와 각도 정보들을 하나의 pair로 저장한 벡터를 새로 만들고, compDegree를 통해서 각도순으로 좌표를 정렬한다. 이때 각도가 같을 경우 좌하단에 있는 점이 먼저 오도록 정렬하였다.

3. convex hull을 구성하는 점들 찾기: convexHull 을 이루는 점들을 저장할 벡터를 만들어서 먼저 P0와 P1을 삽입한다. 그 이후는 벡터에 최근에 저장된 두 개의 점과 그 다음으로 볼 점 degreeSortedVec[i]을 이어서 좌회전하는지 우회전하는지 CCW 함수를 통해서 판단한다. 만약 좌회전을 할 경우 convex hull에 속하는 점이므로 이 점을 convex hull에 넣고 다음 반복으로 넘어간다. 좌회전하지 않을 경우 degreeSortedVec[i]를 제외하고 가장 최근에 넣은 점부터 빼면서 다시 CCW 함수를 호출한다. 이 과정을 좌회전하거나 convex hull에 들어간 점이 2개 미만이 될때까지 반복한다. 

총 7번의 시도 끝에 문제를 맞았다. 형변환, degree 음수 문제, 각도가 같은 경우의 문제가 있었다. 질의응답 게시판의 한 테스트케이스(https://www.acmicpc.net/board/view/60522)가 마지막에 내 코드의 오류를 잡아줘서 풀 수 있었다.

#include <bits/stdc++.h>
#define _USE_MATH_DEFINES

#include <math.h>
using namespace std;

// 1708. Convex Hull - Graham Scan Algorithm
// 1차 수정사항: int를 long으로 수정, 68번 줄 정렬할 때 begin() + 1로 수정  -> 4% 틀렸습니다
// 2차 수정사항: 61번줄 degree가 음수인 경우 PI + degree로 수정 -> 14% 틀렸습니다
// 3차 수정사항: 25~27번줄 일직선에 있는 경우 우선순위 아래쪽, 좌쪽순 정렬 -> 31% 틀렸습니다
// 4차 수정사항: 25~32번줄 compDegree 조금 더 수정

bool comp(pair<int, int> p1, pair<int, int> p2) {
	if (p1.second < p2.second) return true;
	else if (p1.second == p2.second) {
		if (p1.first < p2.first) return true;
		else return false;
	}
	else
		return false;
}

bool compDegree(pair<pair<int, int>, double> p1, pair<pair<int, int>, double> p2) {
	if (p1.second < p2.second) return true;
	else if (p1.second == p2.second) {
		// 일직선에 있는 경우 아래쪽, 좌측이 먼저 정렬
		if (p1.first.second < p2.first.second) return true;
		else if (p1.first.second == p2.first.second) {
			if (p1.first.first < p2.first.first) return true;
			else return false;
		}
		else return false;
	}
	else return false;
}

// 양수면 좌회전, 음수면 우회전, 0이면 일직선 / 양수여야 Convex Hull 속함
long CCW(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3) {
	return (long)(p2.first - p1.first) * (p3.second - p1.second) - (long)(p2.second - p1.second) * (p3.first - p1.first);
}

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

	int n; cin >> n;
	vector<pair<int, int>> vec;

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		vec.push_back(pair<int, int>(a, b));
	}

	// 1. 시작점 찾기 (begin이 시작점)
	sort(vec.begin(), vec.end(), comp);
	pair<int, int> start = vec[0];

	// 2. 각도순 정렬
	vector<double> degrees;
	for (auto p : vec) {
		double degree;
		if (p == start) degree = 0;
		else if (p.first == start.first) degree = M_PI / 2.0;
		else if (p.second == start.second) {
			if (p.first > start.first) degree = 0;
			else degree = M_PI;
		}
		else
			degree = atan((double)(p.second - start.second) / (p.first - start.first));
		if (degree < 0) degree = M_PI + degree;
		degrees.push_back(degree);
		//cout << p.first << ", " <<  p.second << " : " << degree << endl;
	}

	vector<pair<pair<int, int>, double>> degreeSortedVec;
	for (int i = 0; i < vec.size(); i++) {
		degreeSortedVec.push_back(pair<pair<int, int>, double>(vec[i], degrees[i]));
	}
	sort(degreeSortedVec.begin() + 1, degreeSortedVec.end(), compDegree);

	/*for (auto spot : degreeSortedVec) {
		cout << spot.first.first << ", " << spot.first.second << " / " << spot.second << endl;
	}*/

	// 3. convexHull을 구성하는 점들 찾기
	vector<pair<int, int>> convexHull;
	for (int i = 0; i < 2; i++)
		convexHull.push_back(degreeSortedVec[i].first);

	for (int i = 2; i < n; i++) {
		while (convexHull.size() >= 2 && CCW(convexHull[convexHull.size() - 2], convexHull[convexHull.size() - 1], degreeSortedVec[i].first) <= 0)
			convexHull.erase(convexHull.begin() + convexHull.size() - 1); // 좌회전이 될때까지 가장 최근 원소 삭제
		convexHull.push_back(degreeSortedVec[i].first);
	}

	cout << convexHull.size();
}