BOJ 1708 볼록 껍질

사용한 알고리즘

볼록 껍질

알고리즘 설명

볼록 껍질 알고리즘 이다. (기하 너무 무서워요 ㅠ_ㅠ)
라이님 블로그를 참고하였다.
먼저 가장 왼쪽 아래 좌표를 찾는다.
이 좌표를 중심으로 나머지 좌표간에 차이인 dx와 dy 값을 얻는다.
tan^(-1)(dy/dx)는 각도를 나타냄을 안다.
이 각도는 seta 는 0 <= seta < 180 임을 알 수 있다.
나머지 좌표를 각도가 작은 순서로 정렬한다.
이후에 stack에 앞에서 부터 2좌표를 넣고 볼록 껍질을 찾아간다.
stack에서 2개의 좌표를 뽑고, 다음 좌표 next 간에 볼록성을 ccw로 판단한다.
ccw 값이 0 이상인 경우 3 좌표의 관계가 시계방향임을 알 수 있다.
시계방향 관계가 아닌 경우 오목하게 들어간 좌표를 stack에서 제거한다.
위를 반복한뒤 남은 좌표가 볼록 껍질이다.

풀이

// baekjoon 1708 yechan
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int MAX_N = 100001;
const int MAX_INF = 40001;

struct Point{
    int x, y;
    int dx, dy;

    Point(int x, int y, int dx, int dy): x(x), y(y), dx(dx), dy(dy){}
    Point(): Point(0, 0, 1, 0){}
    Point(int x, int y): Point(x, y, 1, 0){}

    bool operator<(const Point &o){
        if (1LL*dy*o.dx != 1LL*o.dy*dx) return 1LL*dy*o.dx < 1LL*o.dy*dx;
        if (dy != o.dy) return dy < o.dy;

        return dx < o.dx;
    }
};

bool ccw(const Point &a, const Point &b, const Point &c) {
    long long x = 1LL*a.x*b.y + 1LL*b.x*c.y + 1LL*c.x*a.y;
    x -= 1LL*a.y*b.x + 1LL*b.y*c.x + 1LL*c.y*a.x;
    return x > 0;
}

int N;
Point pos[MAX_N];

int main() {
    scanf("%d", &N);
    int minPos = 0, minX = MAX_INF, minY=MAX_INF;
    for (int i=0; i<N; i++) {
        scanf("%d%d", &pos[i].x, &pos[i].y);
        if (pos[i].y < minY) {
            minPos = i;
            minY = pos[i].y;
            minX = pos[i].x;
        } else if (pos[i].y < minY){
            if (pos[i].x < minX) {
                minPos = i;
                minX = pos[i].x;
            }
        }
    }
    swap(pos[0], pos[minPos]);

    int cnt_x = pos[0].x;
    int cnt_y = pos[0].y;
    for (int i=1; i<N; i++) {
        pos[i].dx = pos[i].x - cnt_x;
        pos[i].dy = pos[i].y - cnt_y;
    }

    sort(pos+1, pos+N);

    stack<int> st;
    st.push(0);
    st.push(1);
    int next = 2;
    while (next < N) {
        while (st.size() >= 2) {
            int first = st.top();
            st.pop();
            int second = st.top();
            if (ccw(pos[second], pos[first], pos[next])) {
                st.push(first);
                break;
            }
        }
        st.push(next++);
    }
    printf("%d\n", st.size());
    return 0;
}