BOJ 7949 - Cebula 링크
(2024.04.10 기준 P3)

문제

$n$개의 점으로 이루어진 양파가 있다. 양파의 층 하나는 볼록 다각형의 점과 그 가장자리에 포함되는 점으로 구성될 수 있다. 양파를 층으로 분리할 수 있는 최소 횟수 출력

알고리즘

전형적인 볼록 껍질 문제

풀이

$n$개의 점을 모두 포함하게끔 최소 개수의 볼록 다각형을 만들어야 한다. 이는 볼록 껍질을 만들 수 있을 때까지 계속 만들면 됨을 의미한다.

단, 약간의 문제점은 직선인 경우도 포함이다. 그래서 볼록 껍질을 만들고 나서, 그 껍질에 단 한 번이라도 연속하는 세 점이 180도 미만을 이루는지 ccw로 확인해야 한다.
만약 껍질을 이루는 점들이 전부 직선을 이룬다면? 중단하면 된다. 더이상 볼록 껍질을 만들 수 없기 때문이다. (가장 바깥쪽 점들이 직선을 이룬다면, 더 이상 남는 점들이 없다.)

볼록 껍질의 최대 개수를 구하고 남은 점들이 있다면 1을 더해서 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Point{
    ll x, y;
    int i;

    bool operator < (const Point &a) const{
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
};

ll ccw(Point a, Point b, Point c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    while (T--){
        int n; cin >> n;
        if (!n){
            cout << 0 << '\n';
            continue;
        }

        vector<Point> P(n);
        for (int i = 0; i < n; i++) cin >> P[i].x >> P[i].y, P[i].i = i;

        sort(P.begin(), P.end()); // 볼록 껍질을 만들기 위해 정렬
        bool used[n]; memset(used, false, sizeof(used)); // 각 점이 볼록 껍질에 쓰였는지를 저장
        int r = n; // 쓰이지 않은 점의 개수

        int ans = 0; // 만들어진 볼록 껍질의 개수
        while (r >= 3){ // 볼록 껍질은 점이 최소 3개 이상 남아 있어야 한다.
            vector<Point> hull;
            int sz = 0;
            for (int i = 0; i < n; i++){
                if (used[P[i].i]) continue;
                while (sz > 1){
                    if (ccw(hull[sz - 2], hull[sz - 1], P[i]) >= 0) break;
                    hull.pop_back(); --sz;
                }
                hull.push_back(P[i]); ++sz;
            }
            int sz_ = sz;
            hull.pop_back(); --sz;
            for (int i = n - 1; i >= 0; i--){
                if (used[P[i].i]) continue;
                while (sz > sz_){
                    if (ccw(hull[sz - 2], hull[sz - 1], P[i]) >= 0) break;
                    hull.pop_back(); --sz;
                }
                hull.push_back(P[i]); ++sz;
            }
            hull.pop_back(); --sz;

            // 볼록 껍질의 연속하는 세 점이 단 한번이라도 각도가 180도 미만이어야 다각형을 이룬다.
            // 다각형을 이루지 않는 직선이라면 더이상 볼록 껍질을 만들 수 없다.
            bool valid = false;
            for (int i = 0; i < sz; i++)
                if (ccw(hull[i], hull[(i + 1) % sz], hull[(i + 2) % sz]) > 0){
                    valid = true;
                    break;
                }
            if (!valid) break;

            // 쓰인 점을 체크
            for (Point p: hull){
                used[p.i] = true;
                --r;
            }

            ++ans;
        }

        // 남은 점이 있다면 그 자체가 하나의 층이 되므로 1을 더해서 출력
        if (r) cout << ans + 1 << '\n';
        else cout << ans << '\n';
    }
}

• Python (PyPy3)

import sys; input = sys.stdin.readline

def ccw(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])

for _ in range(int(input())):
    n = int(input())
    if not n:
        print(0)
        continue

    P = []
    for i in range(n):
        x, y = map(int, input().split())
        P.append((x, y, i))

    P.sort() # 볼록 껍질을 만들기 위해 정렬
    used = [False] * n # 각 점이 볼록 껍질에 쓰였는지를 저장
    r = n # 쓰이지 않은 점의 개수

    ans = 0 # 만들어진 볼록 껍질의 개수
    while r >= 3: # 볼록 껍질은 점이 최소 3개 이상 남아 있어야 한다.
        hull = []
        for i in range(n):
            if used[P[i][2]]:
                continue
            while len(hull) > 1:
                if ccw(hull[-2], hull[-1], P[i]) >= 0:
                    break
                hull.pop()
            hull.append(P[i])
        sz = len(hull)
        hull.pop()
        for i in range(n - 1, -1, -1):
            if used[P[i][2]]:
                continue
            while len(hull) > sz:
                if ccw(hull[-2], hull[-1], P[i]) >= 0:
                    break
                hull.pop()
            hull.append(P[i])
        hull.pop()

        # 볼록 껍질의 연속하는 세 점이 단 한번이라도 각도가 180도 미만이어야 다각형을 이룬다.
        # 다각형을 이루지 않는 직선이라면 더이상 볼록 껍질을 만들 수 없다.
        valid = False
        for i in range(len(hull)):
            if ccw(hull[i], hull[(i + 1) % len(hull)], hull[(i + 2) % len(hull)]) > 0:
                valid = True
                break
        if not valid:
            break

        # 쓰인 점을 체크
        for x, y, i in hull:
            used[i] = True
            r -= 1

        ans += 1

    # 남은 점이 있다면 그 자체가 하나의 층이 되므로 1을 더해서 출력
    if r:
        print(ans + 1)
    else:
        print(ans)