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

1708번: 볼록 껍질

Convex hull

 

jarvis march와 graham scan 알고리즘은 그림도 없고, 설명도 많이 부족하니 다른 분들의 글을 참고해주세요

 

코드는 determinant를 사용한 풀이입니다

---

1. 문제 해결 아이디어

 

Convex hull 문제를 해결하기 위한 대표적인 2가지 알고리즘에는

1. Jarvis march(gift wrapping) 알고리즘
2. Graham scan 알고리즘

위 2개가 있다.

 

 

Jarvis march(gift wrapping)

 

https://ko.wikipedia.org/wiki/%EC%84%A0%EB%AC%BC_%ED%8F%AC%EC%9E%A5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

점의 개수 : N

볼록 껍질을 이루는 점의 개수 : K

 

가장 왼쪽의 한 점을 시작점으로 둔다.

현재 점을 기준으로 반시계 방향이면서 가장 각도가 큰 점을 찾는다.

-> O(KN)

 

https://youtu.be/ZnTiWcIznEQ

 

 

Graham scan 알고리즘

https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%A0%88%EC%9D%B4%EC%97%84_%EC%8A%A4%EC%BA%94

 

위 gif는 jarvis march에 비해 빠르게 볼록 껍질을 구할 수 있음을 보여준다.

 

 

시작점은 일반적으로 y값이 가장 작은 점으로 정하고 다른 모든 좌표는 시작점에대한 상대좌표를 가지게 된다.

 

시작점에 대한 상대 좌표를 모두 구했다면 시작점을 기준으로 각도 정렬이 가능하다. (반시계 방향)

임의의 두 상대 좌표를 통해 구한 determinant는 시작점을 포함한 삼각형의 넓이라고 볼 수 있고,

determinant가 만약 음수라면 반시계방향이 아니라는 뜻이므로 false를 리턴해서 둘의 위치를 바꿔준다.

determinant가 0이라면 세 점은 한 직선상에 있다는 뜻이므로 상대좌표의 내적이 더 작은 값이 앞에 오도록 해준다.

 

각도 정렬이 끝났다면 볼록 껍질을 구할 차례이다.

 

 

Stack을 사용한다.

 

현재 st번째 점과 mid, ed번째 점을 통해서 이들이 서로 반시계 방향이면 ed번째 점을 stack에 포함시켜 주고 ed를 증가시켜준다.

하지만 중간에 시계 방향이 된다면 증가한 ed는 그대로두고 (ed까지 탐색을 했기때문에 더 이상 되돌아가지 않는다) stack.pop을 한다. 

ex) stack에 0-1-2가 있고 현재 ed가 3이다

     1,2,3번 점을 ccw 해보니 시계 방향이 나온다.

     2를 pop하고 0,1,3과 ccw를 해보니 반시계 방향이 나온다.

     stack에 0-1-3이 있고 현재 ed가 4가 된다.

     위 작업을 반복한다.

 

시작점에 대해서 각도 정렬이 되어있기 때문에 ed를 순차적으로 증가시킬 수 있고

따라서 시간복잡도는 정렬하는 과정에만 영향을 받게 된다.

-> O(NlogN)

 

---

2. 코드

Graham Scan 알고리즘을 사용했다.

N <= 100,000 이므로 NlogN 알고리즘을 사용해야한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
 
#define ll long long
using namespace std;
 
struct P{
    ll x, y;
    ll p, q;
    P(ll x = 0, ll y = 0) : x(x), y(y), p(0), q(0) {}
};
 
int N;
P points[100001];
 
int CCW(const P &p1, const P &p2, const P &p3){
    ll res = (p1.x*p2.y + p2.x*p3.y + p3.x*p1.y) - \
                    (p2.x*p1.y + p3.x*p2.y + p1.x*p3.y);
    if(res > 0) return 1;   //반시계
    else if(res < 0) return -1;     //시계
    else return 0;
}
 
ll det(const P &p1, const P &p2){
    ll res = (p1.p * p2.q - p1.q * p2.p);
    return res;
}
 
bool angle_sort(P &p1, P &p2){
    if(p1.p != 0 || p1.q != 0 || p2.p != 0 || p2.q != 0){
        if(det(p1, p2) > 0){
            return true;
        }
        else if(det(p1, p2) == 0){
            return p1.p*p1.p + p1.q*p1.q < p2.p*p2.p + p2.q*p2.q;
        }
        else{
            return false;
        }
    }
    if(p1.y == p2.y){
        return p1.x < p2.x;
    }
    else return p1.y < p2.y;
}
 
void convex_hull(){
    vector<int> stk;
    
    sort(points, points+N, angle_sort);
    
    for(int i = 1; i < N; i++){
        points[i].p = points[i].x - points[0].x;
        points[i].q = points[i].y - points[0].y;
    }
    
    sort(points+1, points+N, angle_sort);
    
    int st, mid, ed = 2;
    stk.push_back(0); stk.push_back(1);
    
    while(ed != N){    // ed는 마지막 점까지 확인
        while(stk.size() >= 2){     //mid 고정
            mid = stk.back();
            stk.pop_back();
            st = stk.back();
            
            if(CCW(points[st], points[mid], points[ed]) > 0){
                // 반시계 방향인 경우 mid는 convex hull에 임시 포함
                stk.push_back(mid);
                break;
            }
        }
        stk.push_back(ed++);
    }
    
    cout << stk.size();
}
 
void input(){
    int a, b;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> a >> b;
        points[i] = P(a, b);
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    input();
    convex_hull();
    
    return 0;
}