백준 1708번 볼록 껍질

문제 링크입니다: https://www.acmicpc.net/problem/1708

그라함 스캔의 원리를 이용해 풀어야 하는 문제였습니다.

그라함 스캔의 원리는 아래와 같습니다.

1. 점들의 집합에서 y의 좌표가 가장 작거나 y의 좌표가 같다면 x 좌표가 가장 작은 점을 찾아 pivot(기준점)으로 잡습니다.

2. pivot을 기준으로 점들을 반시계 방향으로 정렬합니다. 이 때, 두 벡터의 방향이 같다면 y의 좌표를 기준으로(y의 좌표가 같다면 x의 좌표를 기준으로) 오름차순 정렬을 해줍니다.

3. 반시계 방향으로 정렬한 점들 중 스택에 0번 점과 1번 점을 순서대로 넣고 알고리즘을 진행합니다.

4. 이제 두 번째 점부터 볼록 껍질에 해당하는지 살펴보는데 0 번째 점(first), 첫 번째 점(second)에 대해 두 번째 점(next)가 반시계 방향에 있는지 확인하고, 반시계 방향이라면 스택에 2번 점을 넣어줍니다.

5. 4번을 모든 점에 대해 반복해줍니다.

같은 학교 학우이신 jongwook123님의 ppt를 기반으로 코드를 작성하였고 ccw에 대해 보다 자세한 설명을 알고 싶다면 데구리 블로그(https://degurii.tistory.com/47)를 참고하면 좋을 것 같습니다.

*최근 안드로이드를 집중적으로 공부하느라 알고리즘에 조금 소홀해진 경향이 있는데 다시 마음 잡고 공부를 해야할 것 같습니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <stack>

#include <cmath>

using namespace std;

 

const double PI = 2.0 * acos(0.0);

 

struct vec

{

        double x, y;

        double p, q; //상대적 좌표

 

        vec(double a = 0.0, double b = 0.0) :x(a), y(b), p(0), q(0)

        {

        }

 

        //반시계 방향으로 정렬

        bool operator<(const vec &v)

        {

                 if (1LL * q * v.p != 1LL * p * v.q)

                         return 1LL * q * v.p < 1LL * p * v.q;

 

                 if (y != v.y)

                         return y < v.y;

                 return x < v.x;

        }

 

        //외적

        double cross(const vec &v) const

        {

                 return x * v.y - y * v.x;

        }

};

 

double ccw(vec a, vec b)

{

        return a.cross(b);

}

 

//점 p를 기준으로 벡터 b가 a의 반시계 방향이면 양수, 시계 방향이면 음수

//평행이면 0을 반환

double ccw(vec p, vec a, vec b)

{

        return ccw(vec(a.x - p.x, a.y - p.y), vec(b.x - p.x, b.y - p.y));

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        vector<vec> p(N);

        for (int i = 0; i < N; i++)

                 cin >> p[i].x >> p[i].y;

 

        sort(p.begin(), p.end());

        vec pivot = p[0]; //기준

        for (int i = 1; i < N; i++)

        {

                 p[i].p = p[i].x - pivot.x;

                 p[i].q = p[i].y - pivot.y;

        }

        sort(p.begin() + 1, p.end());

 

        vector<vec> hull;

        hull.push_back(pivot);

        hull.push_back(p[1]);

 

        int next = 2;

        while (next < p.size())

        {

                 while (hull.size() >= 2)

                 {

                         vec first, second;

                         second = hull.back();

                         hull.pop_back();

                         first = hull.back();

                         //반시계 방향일 경우에만

                         if (ccw(first, second, p[next]) > 0)

                         {

                                 hull.push_back(second);

                                 break;

                         }

                 }

                 hull.push_back(p[next++]);

        }

       

        cout << hull.size() << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~