BOJ 1708 볼록 껍질

1 개요

BOJ 1708 볼록 껍질
2 C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
struct Point {
    int x, y;
};
int N;
vector<Point> points;

int ccw(Point a, Point b, Point c) {
    ll cross = 1LL * (b.x - a.x) * (c.y - b.y) - 1LL * (b.y - a.y) * (c.x - b.x);
    return (cross > 0) - (cross < 0);
}

void solve() {
    for (int i = 0; i < N; i++) {
        if (points[i].y < points[0].y || (points[i].y == points[0].y && points[i].x < points[0].x)) {
            swap(points[i], points[0]);
        }
    }
    sort(points.begin() + 1, points.end(), [&](Point a, Point b) {
        int temp = ccw(points[0], a, b);
        if (temp) return temp > 0;
        return a.y < b.y || (a.y == b.y && a.x < b.x);
    });
    vector<Point> hull = { points[0], points[1] };
    for (int i = 2; i < N; i++) {
        while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    cout << hull.size();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    points.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> points[i].x >> points[i].y;
    }
    solve();
}