[백준] 2699번: 격자점 컨벡스헐 (P5) (C++)

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

알고리즘

기하학, 볼록 껍질

문제 요약

각 테스트 케이스에 대해 격자점들을 입력받고,
볼록 껍질을 이루는 꼭짓점들을 특정 순서로 나열하는 문제입니다.

풀이

1708번: 볼록 껍질 문제와 거의 똑같습니다. 사용했던 볼록 껍질 알고리즘도 수정할 필요 없습니다.
볼록 껍질을 이루는 점들을 구하고, 문제에 주어진 기준에 따라 '첫 번째 꼭짓점' 의 위치를 찾아 시계방향 순서대로 나열하면 됩니다.
보통 볼록 껍질 알고리즘을 반시계방향으로 구현하니, 적절하게 기준 꼭짓점으로부터 역방향 또는 정방향으로 출력하면 됩니다.

코드 (요약)

#pragma clang optimize on

#include <iostream>
#include <type_traits>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T, typename U> requires is_integral_v<T> && is_integral_v<U>
struct IPoint {
    T x, y;

    IPoint(T x_, T y_) : x(x_), y(y_) {}

    bool operator<(const IPoint &other) const {
        return less_x(*this, other);
    }

    static bool less_x(const IPoint &p1, const IPoint &p2) {
        return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
    }

    static bool less_y(const IPoint &p1, const IPoint &p2) {
        return p1.y == p2.y ? p1.x < p2.x : p1.y < p2.y;
    }

    static U dist(const IPoint &p1, const IPoint &p2) {
        const U dx = (U) p2.x - p1.x;
        const U dy = (U) p2.y - p1.y;
        return dx * dx + dy * dy;
    }

    static i8 ccw(const IPoint &p1, const IPoint &p2, const IPoint &p3) {
        const U r = ((U) p1.x * p2.y + (U) p2.x * p3.y + (U) p3.x * p1.y) -
                    ((U) p1.y * p2.x + (U) p2.y * p3.x + (U) p3.y * p1.x);
        return r ? (r > 0 ? 1 : -1) : 0;
    }

    static vector<IPoint> convex_hull(vector<IPoint> &ps) {
        swap(ps[0], *min_element(v_all(ps)));
        sort(ps.begin() + 1, ps.end(), [&ps](const IPoint &p1, const IPoint &p2) {
            const i8 r = ccw(ps[0], p1, p2);
            return r ? r > 0 : (U) p1.x + p1.y < (U) p2.x + p2.y;
        });
        vector<IPoint> hull;
        for(IPoint p: ps) {
            while(hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), p) <= 0) {
                hull.pop_back();
            }
            hull.push_back(p);
        }
        return hull;
    }
};

using Pt = IPoint<i16, i16>;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    usize t;
    cin >> t;

    repeat(t) {
        usize n;
        cin >> n;

        vector<Pt> ps;
        ps.reserve(n);
        repeat(n) {
            i16 x, y;
            cin >> x >> y;
            ps.emplace_back(x, y);
        }

        const vector<Pt> hull = Pt::convex_hull(ps);

        const auto it = min_element(v_all(hull), [](const Pt &p1, const Pt &p2) {
            return p1.y == p2.y ? p1.x < p2.x : p1.y > p2.y;
        });
        const usize st = it - hull.begin();

        cout << hull.size() << "\n";
        bool init = true;
        for(usize i = st; init || i != st; i ? i-- : i = hull.size() - 1) {
            cout << hull[i].x << " " << hull[i].y << "\n";
            init = false;
        }
    }

    return EXIT_SUCCESS;
}

여담

한 줄에 좌표가 5개씩 주어진다고 해서 이게 무슨 의미지 하고 오랫동안 헤맸습니다..