볼록 껍질

 

convex hull 알고리즘을 구현하는 문제이다.

알고리즘 자체는 엄청 간단한데, 일단 기준점을 하나 잡고 정렬을 해야 한다.

아래에 있을수록, 왼쪽에 있을수록 작다는 기준으로 정렬을 해서 아래 왼쪽의 점 하나를 기준점으로 잡고,

그 기준점을 기준으로 시계 방향에 있을수록 작다는 기준으로 또 한번 정렬을 한다.

여기서 시계 방향에 있는지, 반시계 방향에 있는지를 구하는 알고리즘이 ccw이다.

ccw는 벡터 외적으로 구하는데, 2차원 평면 상에서 벡터를 외적하면 k성분만 남는데, 이 방향이 시계 방향일 때는 +z방향,

반시계 일때는 -z방향이라는 특징을 이용한다.

 

이제 점들을 돌면서 스택에 넣는다. 

 스택의 상위 2개 점 a,b를 뽑고, 봐야 할 점 c가 있을 때, bc가 ab보다 반시계 방향에 있으면 스택에 넣고,

아니면 스택에서 하나를 pop하고 다시 본다. 이렇게 c가 반시계 방향에 있을 때까지 스택에서 pop을 진행하고,

조건을 만족하면 push해준다. 

이를 반복하면 끝이다.

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
vector<pair<long long,long long>> convex;
stack<int>point;
int ccw(pair<long long,long long>a, pair<long long,long long>b, pair<long long,long long>c) //참이면 반시계, 거짓이면 시계
{
    pair<long long,long long>ab = make_pair(b.first-a.first,b.second-a.second);
    pair<long long,long long>bc = make_pair(c.first-b.first,c.second-b.second);
    long long v = (long long)ab.first*bc.second - (long long)ab.second*bc.first;
    if(v>0) return 1;
    else if(v<0) return -1;
    else return 0;
}
bool cmp1(pair<long long,long long>a, pair<long long,long long>b)
{
    if(a.second==b.second) return a.first<b.first;
    return a.second<b.second;
}
bool cmp2(pair<long long,long long>a, pair<long long,long long>b)
{
    if(ccw(convex[0],a,b)==0)
    {
        return (a.first - convex[0].first) * (a.first - convex[0].first)
             + (a.second - convex[0].second) * (a.second - convex[0].second)
             < (b.first - convex[0].first) * (b.first - convex[0].first)
             + (b.second - convex[0].second) * (b.second - convex[0].second);
    }
    else if(ccw(convex[0],a,b)==1) return true;
    else return false;
}
int main()
{
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        long long a,b;
        scanf("%lld %lld",&a,&b);
        convex.push_back(make_pair(a,b));
    }
    sort(convex.begin(),convex.end(),cmp1);
    sort(convex.begin()+1,convex.end(),cmp2);
    point.push(0);
    point.push(1);
    int next = 2;
    while(next<N)
    {
        while(point.size()>=2)
        {
            int first,second;
            first = point.top();
            point.pop();
            second = point.top();
            if(ccw(convex[second],convex[first],convex[next])==1)
            {
                point.push(first);
                break;
            }
        }
        point.push(next);
        next++;
    }
    printf("%d",point.size());
}

구현 코드이다.