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

인간몽쉘김통통·2025년 3월 22일

백준 볼록 껍질 알고리즘

백준

목록 보기

91/92

문제

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

이해

2차원 평면 상의 N개의 점이 주어질 때 볼록한 다각형을 만들어야 한다. 볼록한 다각형의 정의는 모든 내각이 180도 이하인 다각형이다.

문제를 단순하게 이해하자면 N개의 점 중에서 몇 개를 뽑아 모든 점들을 포함하는 도형을 만들면 된다.

접근

초기에는 기울기에 관한 문제인 줄 알았다. 모든 점들을 y기준으로 정렬하고 모든 점과의 기울기를 계산하고 경계값인 점을 뽑으려 했다. 하지만 기울기의 경계 범위가 위치에 따라 달라진다는 점과 N^2의 시간복잡도를 가지기에 불가능했다.

조금 더 알아보니 볼록껍질(Convex Hull) 알고리즘이 따로 있었다. 볼록 껍질 알고리즘은 정렬과 CCW를 활용한 알고리즘으로 볼록 다각형을 구성하는 점들을 구할 수 있다. 과정을 살펴보자.

정렬하기
우선 점들을 왼쪽 아래를 기준으로 정렬하도록 한다. 가장 첫번째 점은 모든 점들 중 가장 좌하단으로 오게 된다. 첫번째 점을 기준으로 반시계 방향으로 다른 점들을 정렬한다. CCW를 활용하여 첫번째 점을 제외한 점들을 비교하고 CCW 값 내림차순으로 정렬하면 반시계 방향으로 정렬할 수 있다.
다각형 만들기
스택을 활용해 다각형을 만든다. 첫번째, 두번째 점을 초기에 스택에 넣는다. 그 후 모든 점들을 순회해야 한다. i번째 점을 순회할 때, i-1, i-2번째 점과의 CCW를 계산하고 만일 반시계 방향이라면 스택에 삽입한다. 하지만 시계 방향이라면 반복문을 돌려 반시계가 나올 때까지 스택을 pop한다.
개수 세기
최종적으로 스택의 크기가 볼록 껍질을 이루는 점들의 개수가 된다.

풀이

[Sort]

class Point {
public:
    ll x;
    ll y;

    bool operator<(const Point &other) const {
        return (y == other.y ? x < other.x : y < other.y);
    }
};

Point를 좌하단으로 정렬하기 위해 operator<를 오버라이딩했다. 첫번째 점을 뽑은 뒤에는 나머지 점들을 정렬하기 위해 따로 cmp함수를 정의했다.

bool cmp(Point &a, Point &b) {
    ll ccw = CCW(p, a, b);
    if (ccw == 0) {
        return getDistance(p, a) < getDistance(p, b);
    } else {
        return ccw > 0;
    }
}

p는 첫번째 점으로 정렬 기준이 된다. 나머지 두 점과의 ccw를 계산하고 CCW 내림차순으로 정렬했다.

void sortPoints(vector<Point> &points) {
    sort(points.begin(), points.end());
    p = points[0];
    sort(points.begin() + 1, points.end(), cmp);
}

[다각형 만들기]

int ConvexHull(const vector<Point> &points) {
    Point *stk = new Point[points.size()];
    int topIdx = 0;

    stk[0] = points[0];
    stk[1] = points[1];
    topIdx = 1;
    for (int i = 2; i < points.size(); i++) {
        while (true) {
            if (topIdx < 1) {
                break;
            }
            ll ccw = CCW(stk[topIdx - 1], stk[topIdx], points[i]);
            if (ccw <= 0) {
                topIdx--;
            } else {
                break;
            }
        }
        stk[++topIdx] = points[i];
    }

    return topIdx + 1;
}

스택에 0번, 1번 점들을 삽입하고 시뮬레이션을 돌린다. 현재 스택 개수가 1개 미만이라면 그냥 삽입하고 아니라면 CCW를 계산한다. 다음 점이 일직선에 있거나 시계 방향이라면 pop하고 반시계 방향이라면 내부 while을 break하고 스택에 삽입한다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

class Point {
public:
    ll x;
    ll y;

    bool operator<(const Point &other) const {
        return (y == other.y ? x < other.x : y < other.y);
    }
};

ll CCW(Point A, Point B, Point C) {
    ll c = (A.x * B.y) + (B.x * C.y) + (C.x * A.y) - (B.x * A.y) - (C.x * B.y) - (A.x * C.y);
    return c;
}

ll getDistance(Point A, Point B) {
    return (A.x - B.x) * (A.x - B.x) +
           (A.y - B.y) * (A.y - B.y);
}

Point p;

bool cmp(Point &a, Point &b) {
    ll ccw = CCW(p, a, b);
    if (ccw == 0) {
        return getDistance(p, a) < getDistance(p, b);
    } else {
        return ccw > 0;
    }
}

void input(vector<Point> &points) {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        points.push_back({x, y});
    }
}

void sortPoints(vector<Point> &points) {
    sort(points.begin(), points.end());
    p = points[0];
    sort(points.begin() + 1, points.end(), cmp);
}

int ConvexHull(const vector<Point> &points) {
    Point *stk = new Point[points.size()];
    int topIdx = 0;

    stk[0] = points[0];
    stk[1] = points[1];
    topIdx = 1;
    for (int i = 2; i < points.size(); i++) {
        while (true) {
            if (topIdx < 1) {
                break;
            }
            ll ccw = CCW(stk[topIdx - 1], stk[topIdx], points[i]);
            if (ccw <= 0) {
                topIdx--;
            } else {
                break;
            }
        }
        stk[++topIdx] = points[i];
    }

    return topIdx + 1;
}

int main() {
    vector<Point> points;
    input(points);
    sortPoints(points);
    int size = ConvexHull(points);
    cout << size << endl;
}