[1708번] 볼록 껍질(Convex Hull)

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

대표적인 기하알고리즘 문제

풀이 방법은 보통 3가지가 있다.

1. Jarvis March 알고리즘 : O(NH)

1) 주어진 정점에서 극단점 중 하나를 찾는다.

(극단점 : 볼록 외피의 정점이 되는 점, 보통 x좌표나 y좌표가 제일 크거나 작은점을 선택한다. 이 점들은 반드시 극단점에 포함된다.)

2) 다음 극단점 찾기 : 현재까지 찾은 마지막 극단점 다음에 올 극단점을 모든 점을 보면서 탐색

3) 찾은 극단점이 처음 찾은 극단점일 떄 까지 반복

2. Graham Scan 알고리즘 : O(NlogN)

1) 시작점으로 사용할 극단점 선택

2) 시작점을 (0,0)기준으로 모든 점을 평행이동.

3) 각 점들을 각도 정렬해서 각도가 적은 순서대로 방문

4) CCW(마지막 직전점, 마지막 점, 새로운 점)을 해서 오목관계인지 확인하고 오목관계이면 새로운 점을 제외하고 다음 점으로 CCW

5) 반복

3. Monotone Chain 알고리즘 : O(NlogN)

Graham Scan알고리즘에서 시작점을 원점으로 이동한 만큼 평행하는 이유는 각도 정렬할 때, tan 공식을 이용해서 각도를 구하기 위해서다.

두 점A(x1,y1), B(x2,y2)의 각도를 구하는 공식은  θ = atan(y2-y1/x2-x1) 인데 한 점이 원점이면 계산이 편해진다.

#include <iostream>
#include <math.h>
#include <algorithm>
#define MAX 100002
#define px(i) p[i].first
#define py(i) p[i].second
#define pa(i) p[i].angle
using namespace std;
typedef long long ll;
struct P { ll first, second; double angle; };
 
int N;
P p[MAX];
P ST[MAX];
 
ll ccw(P A, P B, P C) {
    ll tmp1 = A.first*B.second + B.first*C.second + C.first*A.second;
    ll tmp2 = B.first*A.second + C.first*B.second + A.first* C.second;
    if (tmp1 - tmp2 < 0)return -1;
    else if (tmp1 - tmp2 > 0)return 1;
    else return 0;
}
 
bool comp1(const P &A, const P &B) {
    if (A.first < B.first) return true;
    else if (A.first == B.first) return A.second < B.second;
    else return false;
}
 
bool comp2(const P &A, const P &B) {
    if (A.angle < B.angle) return true;
    else if (A.angle == B.angle) {
        if(A.first == B.first) return A.second < B.second;
        else return A.first < B.first;
    }
    else return false;
}
 
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> px(i) >> py(i);
    }
    sort(p+1, p + N+1, comp1);
    P origin = p[1];
    for (int i = 1; i <= N; i++) {
        px(i) -= origin.first;
        py(i) -= origin.second;
        pa(i) = atan2(py(i), px(i));
    }
    
    sort(p + 2, p + N+1, comp2);
 
    int nn_p = 1;
    int top = 0;
    while (nn_p <= N) {
        while (top > 1 && ccw(ST[top - 1], ST[top], p[nn_p]) <= 0) 
            top--;
        ST[++top] = p[nn_p++];
    }
    cout << top;
    return 0;
}