Algorithm - Convex Hull (블록 껍질)

개념

Convex Hull이란 2차원 평면 위에 점들이 있을 때 최소한의 정점으로 다른 정점들을 감싸는 알고리즘이다.

Convex Hull

대표적인 알고리즘으로 Graham's Scan(그라함 스캔)이 있다.

Graham's Scan

---

작동원리

1. 정점을 반 시계 or 시계 방향으로 정렬한다.

2. Graham's Scan 알고리즘을 이용한다.

---

시간복잡도

정점을 정렬할 때 -> nlogn, Graham's Scan할 때 -> n

-> O(nlogn)

---

문제

1708 블록 껍질

www.acmicpc.net/problem/1708

1708번: 볼록 껍질

---

코드

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

constexpr int COUNTER_CLOCK_WISE = 1;
constexpr int CLOCK_WISE = -1;
constexpr int STRAIGHT = 0;

class Point {
public:
    long long x, y;

    explicit Point(long long x = 0L, long long y = 0L) : x(x), y(y) {

    }
};

int ccw(Point p1, Point p2, Point p3) {
    long long l = p1.x * p2.y + p2.x * p3.y + p3.x * p1.y;
    long long r = p2.x * p1.y + p3.x * p2.y + p1.x * p3.y;

    if (l - r > 0) {
        return COUNTER_CLOCK_WISE;
    }else if(l - r < 0) {
        return CLOCK_WISE;
    } else {
        return STRAIGHT;
    }
}

int n;
vector<Point> ve;

bool Ascending(const Point &p1, const Point &p2) {
    if (p1.x != p2.x) {
        return p1.x < p2.x;
    }

    return p1.y < p2.y;
}

bool CounterClockWiseSort(const Point &p1, const Point &p2) {
    int result = ccw(ve[0], p1, p2);

    if (result != STRAIGHT) {
        return result == COUNTER_CLOCK_WISE;
    }

    return Ascending(p1, p2);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr);

    cin >> n;
    for (int i = 0;i < n;++i) {
        long long x, y;
        cin >> x >> y;

        ve.emplace_back(x, y);
    }

    sort(ve.begin(), ve.end(), Ascending);
    sort(ve.begin() + 1, ve.end(), CounterClockWiseSort);

    int next = 2;
    stack<int> st; st.push(0); st.push(1);
    while (next < n) {
        while (st.size() >= 2) {
            int v1 = next;
            int v2 = st.top();st.pop();
            int v3 = st.top();

            if (ccw(ve[v3], ve[v2], ve[v1]) == COUNTER_CLOCK_WISE) {
                st.push(v2);
                break;
            }
        }

        st.push(next++);
    }

    cout << st.size() << "\n";
}