백준 1708번 : 볼록 껍질 (C++)

접근

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

1708번: 볼록 껍질

기하 문제에 볼록 다각형을 구하는 문제라서 ccw를 이용하는 것이라고 짐작은 했고, 혼자 풀어보려고 이리 저리 헤메다가 결국 실패하고 다른 분의 풀이를 참고하였다. 그 과정에서 sort 의 비교 함수를 제대로 사용해보았다.

이해하고 풀기는 했지만, 아직 누군가에게 설명할 정도로 이해하진 못해서 참고가 된 다른 글을 링크해두고 다음 기회에 설명을 이어나가려고 한다.

https://restudycafe.tistory.com/386

[C++ 백준 풀이][Platinum] 1708번 : 볼록 껍질 (Convex Hull 알고리즘)

코드

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 100001

struct POINT {
    long long x;
    long long y;
};

int N;
vector<POINT> Point;
stack<POINT> s;

int ccw(POINT a, POINT b, POINT c) {
    long long res = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (0 < res) {
        return 1;
    } else if (res < 0) {
        return -1;
    } else {
        return 0;
    }
}

bool cmp(POINT a, POINT b) {
    if (a.y == b.y) {
        return a.x < b.x;
    } else {
        return a.y < b.y;
    }
}

bool cmpccw(POINT a, POINT b) {
    int val = ccw(Point[0], a, b);
    if (val) {
        return val > 0;
    } else if (b.y == a.y) {
        return a.x < b.x;
    } else {
        return a.y < b.y;
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    int a, b;
    for (int i = 1; i <= N; i++) {
        cin >> a >> b;
        Point.push_back({a, b});
    }
    sort(Point.begin(), Point.end(), cmp);
    sort(Point.begin() + 1, Point.end(), cmpccw);
    s.push(Point[0]);
    s.push(Point[1]);
    POINT tmp1, tmp2;
    for (int i = 2; i < N; i++) {
        while (s.size() >= 2) {
            tmp2 = s.top();
            s.pop();
            tmp1 = s.top();
            if (ccw(tmp1, tmp2, Point[i]) > 0) {
                s.push(tmp2);
                break;
            }
        }
        s.push(Point[i]);
    }
    cout << s.size() << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!