[C++] 1708 - 볼록 껍질 (플래티넘5)

1. 문제 설명

 

1708번: 볼록 껍질

 

---

2. 아이디어

 

이때는 몰랐는데 기하 알고리즘의 입문 절차나 다름없는 문제였다.

이쪽 분야 알고리즘은 처음 풀어봐서 꽤 힘들었었다.

 

CCW(Counter Clockwise)

세 점이 일직선, 가운데점을 기준으로 반시계, 시계 방향으로 놓여있는 경우를 판단하는 알고리즘과

컨백스 헐(Convex Hull)

2차원 평면상의 여러 점중에 다른 모든 점을 포함할수 있는 볼록 다각형을 찾는 알고리즘

이 두 가지를 알고 있어야 해결할 수 있는 문제다.

 

그런데 이걸 처음보고 어떻게 떠올리나. 뚝배기 깨져보고 공부해야 풀 수 있다.

나중에 풀게 될 기하 문제는 위의 두 가지 알고리즘을 베이스로 깔고 넘어가기 때문에

꼭 이해해보도록 하자.

 

---

3. 코드

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

#define ll long long
#define endl "\n"

using namespace std;

typedef struct s_coordinate {
    ll x, y;
}              t_coor;
vector<t_coor> graph;
int n;

ll ccw(t_coor a, t_coor b, t_coor c) { // 외적의 정의 이용 (사선 공식)
    return (a.x*b.y + b.x*c.y + c.x*a.y) - (a.x*c.y + b.x*a.y + c.x*b.y);
}

bool angle(t_coor a, t_coor b) {
    ll value = ccw(graph[0], a, b);
    
    if (value) {
        return value > 0;
    } else if (a.y != b.y) {
        return a.y < b.y;
    } else {
        return a.x < b.x;
    }
}

void coorSort() {
    for (int i=1; i < n; i++) {
        if (graph[0].y > graph[i].y || (graph[0].y == graph[i].y && graph[0].x > graph[i].x)) {
            ll tmp = graph[0].y;
            graph[0].y = graph[i].y;
            graph[i].y = tmp;

            tmp = graph[0].x;
            graph[0].x = graph[i].x;
            graph[i].x = tmp;
        }
    }
    sort(graph.begin() + 1, graph.end(), angle);
}

int draw_polygon() {
    stack<t_coor> vertex;

    vertex.push(graph[0]); vertex.push(graph[1]);

    for (int i=2; i<n; i++) {
        while (vertex.size() >= 2) {
            t_coor mid = vertex.top(); // 중간 좌표
            vertex.pop();
            t_coor start = vertex.top(); // 현재 좌표

            if (ccw(start, mid, graph[i]) > 0) { // 각이 유효하지 않으면 최신화하지 않음
                vertex.push(mid);
                break;
            }
        }
        vertex.push(graph[i]);
    }

    return vertex.size();
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    graph.resize(n);
    for (int i=0; i < n; i++)
        cin >> graph[i].x >> graph[i].y;

    coorSort();
    cout << draw_polygon();

    return 0;
}