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

문제

• 볼록 껍질(백준1708)

풀이

문제 해석을 하자면,

• 입력으로 주어지는 점들 중에서 극단점(제일 외부의 점)으로 이루어진 볼록 껍질(convex hull)을 구하는 문제이다.

풀이

• 볼록 껍질 알고리즘 방법은 다양한데, 그 중에서 NlogN 복잡도가 나오는 알고리즘으로 구현하겠다.

  1. 우선 기준점을 잡는다. (보통 기준점은 y좌표가 가장 작은 것을 기준으로 한다.)

  2. 그리고 이 기준점으로 하여 다른 점들을 반시계 방향으로 정렬한다. (각에 따라 정렬하면 된다.) => 각에 따라 정렬 핵심

  3. 컨벡스 헐 알고리즘(그라함 스캔(Graham’s Scan) 알고리즘)을 이용한다.
     (스택을 이용한다.)

코드

#include <iostream>
#include <algorithm>
#include <cmath> // atan2
#include<stack>
using namespace std;

struct point {
	long long x; long long y; // 절대위치
	long long p; long long q; // 상대위치
};
typedef point Point;

long long ccw2(Point p, Point q) {
	return p.x * q.y - p.y * q.x;
}

long long ccw(Point r, Point p, Point q) {
	p.x -= r.x; p.y -= r.y;
	q.x -= r.x; q.y -= r.y;
	return ccw2(p, q);
}

int getMaxPointIndex(Point inPoint[], int N) {
	Point p = inPoint[0]; // // 0번째를 초기값으로 설정(값)
	int result = 0; // 0번째를 초기값으로 설정(인덱스)
	for (int i = 0; i < N; i++) {
		if (p.y > inPoint[i].y) {
			p = inPoint[i];
			result = i;
		}
	}
	return result; // index
}

double getAngle(Point a) {
	return atan2(a.q, a.p); // arctan(y,x) => 각도 계산
}

bool comp(Point a, Point b) {
	if (getAngle(a) != getAngle(b)) return getAngle(a) < getAngle(b);
	if (a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}

Point inPoint[100005];
int N;

int main() {
	// input
	cin >> N;
	for (int i = 0; i < N; i++) cin >> inPoint[i].x >> inPoint[i].y;

	// run
	// y좌표, x좌표 기준 오름차순 정렬
	sort(&inPoint[0], &inPoint[N], comp);

	// 기준점(=inPoint[0])기준 상대위치 기록 (따라서 i=1부터)
	for (int i = 1; i < N; i++) {
		inPoint[i].p = inPoint[i].x - inPoint[0].x;
		inPoint[i].q = inPoint[i].y - inPoint[0].y;
	}

	// => 기준점에서 각도 비교로 반시계 정렬하면 됨(기준점 제외)
	sort(&inPoint[1], &inPoint[N], comp);

	// 1st, 2st로 바로 초기값 사용
	stack<int> st; // index 기록하므로 그냥 int자료형 사용
	st.push(0); st.push(1); // 0, 1 index 푸시

	// 전처리 끝
	// 알고리즘 시작
	int next = 2;
	while (next < N) {
		while (st.size() >= 2) {
			int first, second;
			second = st.top();
			st.pop();
			first = st.top();

			// leftTurn 사용
			if (ccw(inPoint[first], inPoint[second], inPoint[next]) > 0) {
				st.push(second);
				break;
			}
		}

		st.push(next++); // next push
	}
	cout << st.size();

	return 0;
}

느낀점

생략