[1708번] 볼록 껍질

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Convex Hull

컨벡스 헐을 이용하여 문제를 풀 수 있는 기본적인 문제이다.

http://www.crocus.co.kr/1288?category=209527

위의 링크를 참고하여 컨벡스 헐 알고리즘을 이해하고 문제를 풀어보자.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
 
#define MAX 100002
 
using namespace std;
 
typedef long long ll;
 
struct Point {
    int x, y;
    int p, q;
    Point(int x1 = 0, int y1 = 0) : x(x1), y(y1), p(1), q(0) {}
};
 
bool comp1(const Point &A, const Point &B) {
    if (A.y != B.y)
        return A.y < B.y;
 
    return A.x < B.x;
}
bool comp(const Point &A, const Point &B) {
    if (1LL * A.q * B.p != 1LL * A.p*B.q)
        return 1LL * A.q * B.p < 1LL * A.p*B.q;
 
    if (A.y != B.y)
        return A.y < B.y;
 
    return A.x < B.x;
}
 
ll ccw(const Point &A, const Point &B, const Point &C) {
    return 1LL * (A.x*B.y + B.x*C.y + C.x*A.y - B.x*A.y - C.x*B.y - A.x*C.y);
}
 
Point p[MAX];
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
 
        p[i] = Point(x, y);
    }
 
    sort(p, p + n, comp1);
 
    for (int i = 1; i < n; i++) {
        p[i].p = p[i].x - p[0].x;
        p[i].q = p[i].y - p[0].y;
    }
 
    sort(p + 1, p + n, comp);
 
    stack<int> s;
 
    s.push(0);
    s.push(1);
 
    int next = 2;
 
    while (next < n) {
        while (s.size() >= 2) {
            int first, second;
            second = s.top();
            s.pop();
            first = s.top();
 
            if (ccw(p[first], p[second], p[next]) > 0) {
                s.push(second);
                break;
            }
        }
 
        s.push(next++);
    }
 
    printf("%d", s.size());
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

STL 사용하지 않고 Convex Hull 구현하고 문제 풀기

#include <iostream>
#include <cstdio>
#include <algorithm>
 
#define MAX 100002
 
using namespace std;
 
typedef long long ll;
 
struct Point {
    int x, y;
    int p, q;
    Point(int x1 = 0, int y1 = 0) : x(x1), y(y1), p(1), q(0) {}
};
 
ll ccw(const Point &A, const Point &B, const Point &C) {
    return 1LL * (A.x*B.y + B.x*C.y + C.x*A.y - B.x*A.y - C.x*B.y - A.x*C.y);
}
 
Point p[MAX];
Point tmp[MAX];
 
bool comp1(const Point &A, const Point &B) {
    if (A.y != B.y)
        return A.y < B.y;
 
    return A.x < B.x;
}
bool comp(const Point &A, const Point &B) {
    if (1LL * A.q * B.p != 1LL * A.p*B.q)
        return 1LL * A.q * B.p < 1LL * A.p*B.q;
 
    if (A.y != B.y)
        return A.y < B.y;
 
    return A.x < B.x;
}
 
void mergeSortComp1(int start, int end) {
    if (start < end) {
        int mid = (start + end) >> 1;
 
        mergeSortComp1(start, mid);
        mergeSortComp1(mid + 1, end);
 
        int left = start, right = mid + 1;
        int idx = start;
 
        while (left <= mid || right <= end) {
            if (right > end || (left <= mid && comp(p[left], p[right]))) {
                tmp[idx++] = p[left++];
            }
            else
                tmp[idx++] = p[right++];
        }
        
        for (int i = start; i <= end; i++)
            p[i] = tmp[i];
    }
}
void mergeSortComp(int start, int end) {
    if (start < end) {
        int mid = (start + end) >> 1;
 
        mergeSortComp(start, mid);
        mergeSortComp(mid + 1, end);
 
        int left = start, right = mid + 1;
        int idx = start;
 
        while (left <= mid || right <= end) {
            if (right > end || (left <= mid && comp(p[left], p[right]))) {
                tmp[idx++] = p[left++];
            }
            else
                tmp[idx++] = p[right++];
        }
 
        for (int i = start; i <= end; i++)
            p[i] = tmp[i];
    }
}
 
 
class stack {
public:
    int capacity, sz;
    int *st;
 
    stack() {
        capacity = 8;
        sz = 0;
        st = new int[capacity];
    }
    ~stack() { delete[] st; }
 
    void push(int val) {
        if (capacity == sz) {
            capacity *= 2;
            int *tmp = new int[capacity];
            for (register int i = 0; i < sz; i++)
                tmp[i] = st[i];
            delete[] st;
            st = tmp;
        }
        st[sz++] = val;
    }
    int top() {
        return st[sz - 1];
    }
    void pop() {
        sz--;
    }
    int size() { return sz; }
    bool empty() { return !sz; }
    void clear() {
        delete[] st;
        capacity = 8;
        sz = 0;
        st = new int[capacity];
    }
};
 
stack s;
int main() {
 
        int n;
        scanf("%d", &n);
 
        for (int i = 0; i < n; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
 
            p[i] = Point(x, y);
        }
 
        mergeSortComp1(0, n - 1);
 
        for (int i = 1; i < n; i++) {
            p[i].p = p[i].x - p[0].x;
            p[i].q = p[i].y - p[0].y;
        }
 
        mergeSortComp(1, n - 1);
 
 
        s.push(0);
        s.push(1);
 
        int next = 2;
 
        while (next < n) {
            while (s.size() >= 2) {
                int first, second;
                second = s.top();
                s.pop();
                first = s.top();
 
                if (ccw(p[first], p[second], p[next]) > 0) {
                    s.push(second);
                    break;
                }
            }
 
            s.push(next++);
        }
 
        printf("%d\n", s.size());
 
    return 0;
}