레야몬

[C++] 1708번 볼록 껍질 - 기하학, 볼록 껍질 본문

알고리즘/백준

[C++] 1708번 볼록 껍질 - 기하학, 볼록 껍질

Leyamon 2022. 10. 3. 19:21
#include <iostream>
#include <algorithm>
#include <stack>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 100001

using namespace std;
typedef long long ll;

struct VEC {  //vector
    int x, y;
    int p, q;
    VEC(int X=0, int Y=0) : x(X), y(Y), p(0), q(0) {}
};

int N;  //점의 개수 N
VEC p[MAX_N];

void input()
{
    cin >> N;
    LOOP(i, N) {
        int x, y;
        cin >> x >> y;
        p[i] = VEC(x, y);
    }
}

bool compare(const VEC &a, const VEC &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(VEC &a, VEC &b, VEC &c)
{
    return 1LL*(a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    sort(p+1, p+N+1, compare);  //제일 아래 왼쪽 좌표
    
    LOOP(i, N-1) {  //상대 벡터 형성
        p[i+1].p = p[i+1].x - p[1].x;
        p[i+1].q = p[i+1].y - p[1].y;
    }
    
    sort(p+2, p+N+1, compare);  //반시계 방향으로 정렬
    
    stack<int> s; s.push(1); s.push(2);
    int next = 3;
    while(next<=N) {
        while(s.size()>=2) {
            int a, b;
            a = s.top(); s.pop();
            b = s.top();
            if(CCW(p[a], p[b], p[next]) < 0) {  //왼쪽에 있으면 ㄱㅊ
                s.push(a);
                break;
            }
        }
        s.push(next++);
    }
    cout << s.size();
    

    return 0;
}

점점... 벡터랑 행렬을 당연하듯이 쓰고 있다. 이게 맞는지는 잘 모르겠는데... 엄.... 그렇다....

 

볼록 껍질 알고리즘은 처음이라서 다른 사이트를 찾아보면서 공부했다. 참고한 사이트는 아래에 있다.

 

 

 

 

<Convex Hull Algorithm>

https://www.crocus.co.kr/1288

 

컨벡스 헐 알고리즘(Convex Hull Algorithm)

목차 1. 컨벡스 헐 알고리즘(Convex Hull Algorithm)이란? 2. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 동작 원리 3. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 구현 4. 관련 문제 1. 컨벡스 헐 알고리즘(..

www.crocus.co.kr

 

 

<이상한 코드? (풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/27512622

 

로그인

 

www.acmicpc.net

 

여기 보면 convex hull algorithm이랑 조금 다른 알고리즘을 사용하는 것 같은 코드가 있는데 12ms가 더 빨리 나왔다. 또 다른 알고리즘인 듯 한데 나중에 공부해봐야겠다.

 

아 그래프에 그려보면서 문제를 풀면 편하다.

https://www.desmos.com/calculator?lang=ko 

 

Desmos | 그래핑 계산기

 

www.desmos.com

 

 

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다

Comments