[C++] 볼록 껍질 (백준 1708번) - 볼록 껍질 (Convex Hull)

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

 

우선 가장 바깥쪽의 점 하나를 고른다. 어느 축으로 봐도 상관 없지만 나는 y값이 가장 작은, y값이 동일하다면 x값이 가장 작은 점을 선택했다. 이 점이 볼록 껍질을 구성할 때 시작점이 된다.

 

아까 고른 시작점을 점 벡터의 첫번째 원소가 되도록 한 다음, 그 점을 기준으로 반시계 방향으로 각도 정렬을 해준다. 나는 compare 함수를 만들어서 sort 함수를 사용할 때 인자로 넣어주어서 정렬했다.

 

그 후 스택을 하나 만들어서 첫 두 점은 일단 넣어주고, 그 다음부터는 스택에서 두번째로 위에 있는 점, 가장 위에 있는 점, 그리고 새로운 점이 볼록을 이루는지 판단하여 점들을 빼고 넣어준다. 볼록하면 그대로 두고 새로운 점을 넣고, 볼록하지 않다면 가장 위에 있는 점을 버리고 다시 판단하고를 반복한 후 볼록해졌을 때 새로운 점을 넣어주고 다음 점으로 넘어간다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

typedef long long ll;

struct Point {
    ll x, y;
};

vector<Point> p;
ll minx = 1e9;
ll miny = 1e9;
int mini = -1;

int ccw(Point &a, Point &b, Point &c) {
    ll res = (a.x * b.y + b.x * c.y + c.x * a.y) - (b.x * a.y + c.x * b.y + a.x * c.y);
    if (res > 0) return 1; // counter clock-wise
    else if (res < 0) return -1; // clock-wise
    else return 0;
}

bool compare(Point &a, Point &b) {
    int ccwv = ccw(p[0], a, b);
    if (ccwv != 0) return ccwv > 0;
    else if (a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

void solve() {
    int n;
    cin >> n;

    p = vector<Point>(n);

    // 기준점 (최외곽 점) 찾기
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
        if (p[i].y < miny || (p[i].y == miny && p[i].x < minx)) {
            minx = p[i].x;
            miny = p[i].y;
            mini = i;
        }
    }

    // p[0]과 p[mini] swap
    p[mini].x = p[0].x;
    p[mini].y = p[0].y;
    p[0].x = minx;
    p[0].y = miny;

    // 각도 정렬
    sort(p.begin() + 1, p.end(), compare);

    // 볼록 껍질 구성 (Graham Scan)
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (s.size() >= 2) {
            int idx2 = s.top();
            s.pop();
            int idx1 = s.top();
            if (ccw(p[idx1], p[idx2], p[i]) > 0) {
                s.push(idx2);
                break;
            }
        }
        s.push(i);
    }

    cout << s.size() << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)