1708번: 볼록 껍질

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

graham scan을 이용한다.

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> point;
long long ccw(point i, point j, point k) {
    return 1LL * (j.x - i.x)*(k.y - i.y) - 1LL * (k.x - i.x)*(j.y - i.y);
}
int n, sz;
point p[100000], stk[100000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y);
    swap(p[0], *min_element(p, p + n));
    sort(p + 1, p + n, [](point i, point j) {
        long long t = ccw(p[0], i, j);
        return t > 0 || !t&&i < j;
    });
    for (int i = 0; i < n; i++) {
        while (sz > 1 && ccw(stk[sz - 2], stk[sz - 1], p[i]) <= 0) sz--;
        stk[sz++] = p[i];
    }
    printf("%d", sz);
    return 0;
}

위, 아래 껍질을 나눠서 구할 수도 있다.

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> point;
point p[100000], low[100000], up[100000];
int n, sl, su;
long long ccw(point i, point j, point k) {
    return 1LL * (j.x - i.x)*(k.y - i.y) - 1LL * (k.x - i.x)*(j.y - i.y);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y);
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        while (sl > 1 && ccw(low[sl - 2], low[sl - 1], p[i]) >= 0) sl--;
        while (su > 1 && ccw(up[su - 2], up[su - 1], p[i]) <= 0) su--;
        low[sl++] = up[su++] = p[i];
    }
    printf("%d", sl + su - 2);
    return 0;
}