백준 1708 볼록 껍질

www.acmicpc.net/problem/1708

 

볼록 껍질 문제는 Convex Hull 문제라고 보면 된다.

 

Convex Hull 문제를 푸는 방식은 두 가지가 있다고 한다.

하나는 Graham Scan 방식과 Jarvis March 방식이다.

 

Jarvis March 방식은 나도 아직 잘 모르겠고,

 

Graham Scan 방식으로 문제를 풀었다.

 

알고리즘 설명은 이렇다.

1. 좌표값들이 주어진다.

2. 모든 좌표 중에서 극좌표를 결정한다.

3. 극좌표 결정은 y 좌표값이 가장 작고, 만약 y값이 같다면 x값이 작은 좌표를 찾아 극좌표로 결정하면 된다.

4. 극좌표를 기준으로 모든 좌표들을 반시계방향으로 좌표를 정렬한다.

5. 이 때, 정렬하는 방식은 ccw 방식을 사용하면 된다.

6. ccw > 0 이라면 반시계 방향이고, ccw == 0 이면 동일한 방향, ccw < 0 이면 시계 방향이라고 생각하면 된다.

7. 만약 ccw == 0 이 나와서 동일한 방향의 좌표가 나타난다면, 거리가 더 가까운 좌표를 먼저 오도록 정렬한다.

8. 정렬이 끝났다면, 처음 두 좌표를 stack에 넣어준다.

9. 첫 좌표를 기준으로 두 번째 좌표는 pop을 하고, 다음 n번째 좌표값과 계산하여 방향을 판단한다.

10. n번째 좌표가 반시계 방향이면 두 번째 좌표는 넣어준다.

11. (여기서 나는 엄청 헤맸다.) 만약 시계 방향이라면 두 번째 pop 되었던 좌표는 다시 stack에 넣어주면 안된다.

11-1. 이제 while문을 돌면서 stack의 사이즈가 2보다 작아지거나 n번째 좌표와 stack의 가장 위 두 좌표가 반시계방향이 나올 때까지 반복한다.

12. 마지막 좌표까지 순환을 하고 나서 최종 stack의 사이즈를 출력해주면 끝이난다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <stdlib.h>
#include <stack>
#include <algorithm>

using namespace std;

struct Coordinate{
	double x, y;
} Polar;
int N;

long long ccw(Coordinate p1, Coordinate p2, Coordinate p3) {
	long long res = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x);
	if (res > 0) return 1; // Counter Clockwise Direction
	else if (res < 0) return -1; // Clockwise Direction
	else return 0; // Same Direction
}

long double distance(Coordinate a, Coordinate b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool compare(Coordinate a, Coordinate b) {
	if (ccw(Polar, a, b) > 0) return true;
	else if (ccw(Polar, a, b) < 0) return false;
	else {
		if (distance(Polar, a) < distance(Polar, b)) {
			return true;
		}
		else {
			return false;
		}
	}
}

int main() {
	scanf("%d", &N);

	Coordinate* nArr = (Coordinate*)malloc(sizeof(Coordinate) * N);

	for (int i = 0; i < N; ++i) {
		scanf("%lf %lf", &nArr[i].x, &nArr[i].y);
	}
	
	// Initialize Polar Coordinate
	Polar = nArr[0];

	// Searching and Renewing Polar Coordinate
	for (int i = 1; i < N; ++i) {
		if (nArr[i].y < Polar.y) {
			Polar = nArr[i];
		}
		else if (nArr[i].y == Polar.y) {
			if (nArr[i].x < Polar.x) {
				Polar = nArr[i];
			}
		}
	}

	sort(nArr, nArr + N, compare);

	stack<Coordinate> s;

	s.push(nArr[0]);
	s.push(nArr[1]);

	Coordinate first, second;

	for (int i = 2; i < N; ++i) {
		while (s.size() >= 2) {
			second = s.top();
			s.pop();
			first = s.top();

			if (ccw(first, second, nArr[i]) > 0) { // 반시계방향
				s.push(second);
				break;
			}
		}

		s.push(nArr[i]);
	}

	printf("%d", s.size());

	return 0;
}