[백준] 1708번: 볼록 껍질

이미지를 클릭하면 문제로 이동합니다.

문제를 풀기에 앞서 알고리즘에서 쓰이는 기하학에 기초에 대해 알고싶다면 다음 포스팅을 참고해주세요. “[Algorithm]기하 기초”

볼록껍질 문제를 접근하는 방법은 세 가지가 있습니다.

1. Jarvis March

1. 주어진 정점 중에서 극단점(extreme point)를 하나 찾습니다.
   • 극단점이란 볼록 외피의 정점이 되는 점입니다
   • x 좌표나 y 좌표가 가장 크거나 작은 점은 반드시 극단점에 포함 됩니다
2. 다음 극단점을 찾습니다
   • 현재까지 찾은 마지막 극단점 다음에 올 극단점을 모든 점을 탐색하여 찾습니다
   • 왼쪽 또는 오른쪽을 선택하여 일관성있는 방향으로 탐색을 합니다
   • 이 과정이 가장 오래 걸립니다
3. 처음 찾은 극단점으로 돌아올 때 까지 과정 2를 반복합니다

이 알고리즘의 시간복잡도는 $O(n^2)$입니다

2. Graham Scam

1. 최하점(x와 y가 모두 가장 작은 점)을 기준점으로 잡고 모든 점들을 각도 순으로 정렬합니다
   • 점들을 각도 순으로 정렬할 때 CCW를 사용하면 쉽게 정렬할 수 있습니다
     • CCW가 음수인 점은 CCW가 양수인 점 보다 기준점으로 부터 각도가 작습니다
   • 각도가 동일한 경우 거리가 가까운 것부터 정렬을 합니다
2. 각도 순으로 탐색하며 오목한 부분이 나오면 그 점을 제거합니다
   • 오목한 부분은 CCW의 값으로 판별할 수 있습니다. CCW 값이 음수가 되면 점들이 시계방향을 있다는 것이므로 오목한 형태를 띄게 됩니다. 이 경우 마지막으로 선택한 점을 빼줍니다
3. 출발점까지 돌아오면 탐색이 끝납니다

이 알고리즘의 시간복잡도는 $O(n \log N)$입니다

3. Monotone Chain

1. x축을 기준으로 정렬합니다. x값이 같은 경우 y축을 기준으로 정렬합니다
   • 정렬이 끝나면 최좌측점은 맨 앞에, 최우측점은 맨 뒤에 위치하게 됩니다
2. 정렬한 순서대로 최좌측점에서 최우측점까지 탐색하며 위로 볼록한 껍질을 이루도록 점을 선택합니다
   • Graham Scan과 마찬가지로 오목해지는 점은 제거해 줍니다
3. 과정 2와 마찬가지로 최좌측점에서 최우측점까지 탐색하며 아래로 볼록한 껍질을 이루도록 점을 선택합니다
   • 마찬가지로 오목해지는 점은 제거해 줍니다
4. 과정 2와 과정 3에서 찾는 점들의 리스트를 병합해주고 최좌측점과 최우측점이 중복되지 않도록 병합된 리스트에서 하나씩 제거해 줍니다

이 알고리즘의 시간복잡도는 $O(n \log N)$입니다

문제 풀이

저는 Graham Scam을 이용해서 문제를 풀었습니다. 먼저 x값과 y값이 모두 제일 작은 최하점을 찾았고 그 다음 CCW를 이용해서 각도정렬을 했습니다. 기준점으로 부터 CCW를 하여 양수인 점이 앞으로 오게 하면 각도정렬을 할 수 있습니다. 다만 세 점이 일직선상에 있는 경우를 주의해야 하는데 저는 기준점을 x와 y값이 모두 작은 점으로 잡았기 때문에 나머지 두 점은 모두 기준점의 오른쪽에 위치하게 됩니다. 따라서 둘 중 기준점과의 거리가 가까운 점을 앞으로 오게 만들어주면 각도정렬이 끝납니다.

그 다음은 모든 점을을 탐색하여 오목해지는 점을 제거해 주어야 합니다. 이 떄 주의할 점은 마지막으로 선택한 점이 n번쨰 점이라고 할 때 CCW(n-1, n, n+1)의 결과가 음수이면 n번째 점을 제거해 주어야 한다는 것입니다. CCW의 부호는 n번째 점이 n-1번째 점과 n+1번째 사이에 어디에 위치하느냐에 따라 달렸기 때문에 n+1번째 점을 제거하는 것이 아닌 n번째 점을 제거해 주어야 합니다.

마지막으로 주의해야할 점은 이 문제에서는 볼록껍질의 변에 여러개의 점이 있는 경우는 가장 양 끝점만 개수에 포함하기 때문에 CCW의 부호가 음수일때 뿐만 아니라 0이 되는 점도 제거를 해 주어야 한다는 것입니다.

이 과정을 끝나고 모든 점을 다 탐색하게 되면 볼록껍질에 포함되는 점의 갯수가 나오게 됩니다.

Code

#include <stdio.h>
#include <algorithm>
#define MAX 100010

using namespace std;

typedef long long int lld;
typedef struct COORD{
    int x, y;
};

// ccw의 부호를 return 하는 함수
int ccw(COORD a, COORD b, COORD c){
    lld  CCW =  ((lld)a.x*b.y + (lld)b.x*c.y + (lld)c.x*a.y) - ((lld)a.y*b.x + (lld)b.y*c.x + (lld)c.y*a.x);
    if (CCW < 0){
        return -1;
    }
    else if (CCW > 0){
        return 1;
    }
    else {
        return 0;
    }
}


int N, cnt, pivot, top;
COORD coord[MAX], stack[MAX];

void swapCoord(int a, int b){
    COORD tmp;
    tmp = coord[a];
    coord[a] = coord[b];
    coord[b] = tmp;
}

// 각도정렬을 해주는 사용자 정의 함수
bool cmp(COORD a, COORD b){
    long long int CCW = ccw(coord[0], a, b);
    if (CCW == 0){
        if (a.x == b.x){
            return a.y < b.y;
        }
        else {
            return a.x < b.x;
        }
    }
    return CCW > 0;
};

void input(){
    scanf("%d", &N);
    pivot = 0;
    for (int i = 0; i < N; i++){
        scanf("%d %d", &coord[i].x, &coord[i].y);
        // x와 y값이 모두 제일 작은 점을 선택
        if (coord[i].x < coord[pivot].x){
            pivot = i;
        }
        else if (coord[i].x == coord[pivot].x && coord[i].y < coord[pivot].y){
            pivot = i;
        }
    }
    swapCoord(0, pivot);
    // 각도정렬
    sort(coord+1, coord+N, cmp);
}

// CCW를 이용하여 오목한 점을 제거하는 함수
void countCCW(){
    for (int i = 0; i < N; i++){
        // 최종 선택에 포함 되는 점들을 stack에 담고 제거해야하는 점들은 pop을 해줌
        while (top > 1 && ccw(stack[top-1], stack[top], coord[i]) <= 0) {
            top--;
        }
        stack[++top] = coord[i];
    }
}

void solve(){
    input();
    countCCW();
    printf("%d\n", top);
}

int main(void){
    solve();
    return 0;
}