Powered by GitBook

볼록 껍질 (Convex Hull)

구현 (Graham's scan)

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long int lld;
lld ccw(struct Point p1, struct Point p2, struct Point p3);

struct Point {
    lld x, y;
    Point *s = NULL;

    bool operator <(const Point &o) const {
        if (s != NULL) {
            lld ret = ccw(*s, *this, o);
            if (ret != 0) return ret > 0;
        }
        if (y != o.y) return y < o.y;
        return x < o.x;
    }
};

lld ccw(struct Point p1, struct Point p2, struct Point p3) {
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}

Point p[100010];

int main()
{
    int n, i;
    vector<int> s;

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%lld%lld", &p[i].x, &p[i].y);

    // 정렬하여 첫 점을 구하고, 다른 값에 첫 점 정보를 입력
    sort(p, p + n);
    for (i = 1; i < n; i++)
        p[i].s = &p[0];

    // 각에 따른 정렬 (반시계 방향)
    sort(p + 1, p + n);

    // 스택을 이용하여 컨벡스헐을 찾음
    s.push_back(0);
    s.push_back(1);
    for (i = 2; i < n; i++) {
        while (s.size() >= 2) {
            int last1 = *(s.end() - 1);
            int last2 = *(s.end() - 2);
            if (ccw(p[last2], p[last1], p[i]) > 0)
                break;
            s.pop_back();
        }
        s.push_back(i);
    }

    printf("%d", s.size());

    return 0;
}

1708 문제 풀이

// 2차원 평면상에 있는 점들을 모두 포함하는 볼록 다각형을 볼록 껍질(convex hull)이라고 한다.
// 전체 시간복잡도는 정렬을 하는 데 필요한 O(NlogN)

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct vec{
    double x, y;
    vec operator -(const vec& rhs) const { return {x-rhs.x, y-rhs.y}; }
    bool operator <(const vec &rhs) const {
        if(y != rhs.y) return y < rhs.y;
        return x < rhs.x;
    }
    double cross(const vec& rhs) const { return x * rhs.y - rhs.x * y; }
};
double ccw(vec a, vec b){ return a.cross(b); }
double ccw(vec p, vec a, vec b){ return ccw(a-p, b-p); }

// 각정렬을 위한 기준점 s
// 각정렬 시 기준점 기준으로 일직선인 경우를 처리 안 해주면 오답이 난다.
// 일직선인 경우 기준점에 더 가까운 점이 정렬 시 더 앞쪽으로 오는데 
// 그렇게 해야지만 (더 멀리 있는 점을 선택하면서) 알고리즘이 올바르게 작동한다.
// 처리를 안 하면 일직선인 점 2개 중 어떤 게 앞에 올 지는 데이터에 따라 다르기 때문에
// 디버깅에서 고생할 수 있다.
vec s;
bool cmp(vec a, vec b){
    if(ccw(a-s, b-s) != 0) return ccw(a-s, b-s) > 0;
    return a < b;
}

vector<int> convex_hull(vector<vec>& p){
    sort(p.begin(), p.end());
    s = p[0];
    sort(p.begin()+1, p.end(), cmp);

    vector<int> ret;
    ret.push_back(0);
    ret.push_back(1);

    for(int now=2; now<p.size(); now++){
        while(ret.size() >= 2){
            int last1 = *(ret.end() - 1);
            int last2 = *(ret.end() - 2);
            // 이상적이다.
            if(ccw(p[last2], p[last1], p[now]) > 0) break;
            ret.pop_back();
        }
        ret.push_back(now);
    }
    return ret;
}

용준이가 작성

정리

Graham's scan : O(NlogN)
정렬하여 오른쪽 아래의 점을 찾는다 (y점이 가장작고, y가 같다면 x점이 가장 작은 한 점)
ccw 함수를 통해서 (첫점-현재-비교 가 반시계방향으로) 정렬한다.
스택을 이용해서, 이전 두개와 다음점이 반시계 방향이 아닐 경우 스택에서 제외하여, 모든 점이 반시계 방향이 되도록 넣는다.
스택에 들어간 점은 컨벡스헐을 이루고 있다.

관련 문제

1708번: 볼록 껍질
6850번: Cows
17403번: 가장 높고 넓은 성
2254번: 감옥 건설 (★)
7420번: 맹독 방벽
3878번: 점 분리 (★)
9240번: 로버트 후드 (★)
10254번: 고속도로 (★)

참고 자료

results matching ""

No results matching ""