BOJ 6962 - Maple Roundup 링크
(2023.05.25 기준 P5)

문제

좌표 (x, y)로 표시되는 나무 n개가 주어진다. 이 나무들을 리본으로 감싸려고 하며 모든 나무들이 리본 안에 들어가야 한다면, 최소 리본 길이 출력

알고리즘

볼록 껍질

풀이

모든 나무들이 포함되게끔 나무들을 리본으로 감싼다는 말은 즉, 나무들의 볼록 껍질인 것이다.

이 볼록 껍질을 구하고 볼록 껍질의 모든 변의 길이를 합쳐 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

int ccw(pii a, pii b, pii c){
    return (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}

double dist(pii a, pii b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void solve(){
    int n; cin >> n;
    vector<pii> points(n);
    for (int i = 0; i < n; i++) cin >> points[i].x >> points[i].y;
    sort(points.begin(), points.end());

    // 볼록 껍질의 아래
    vector<pii> hull;
    int SZ = 0;
    for (int i = 0; i < n; i++){
        while (SZ > 1){
            if (ccw(hull[SZ - 2], hull[SZ - 1], points[i]) > 0) break;
            hull.pop_back(); SZ--;
        }
        hull.push_back(points[i]); SZ++;
    }

    // 볼록 껍질의 위
    int sz = SZ;
    for (int i = n - 1; i >= 0; i--){
        while (SZ > sz){
            if (ccw(hull[SZ - 2], hull[SZ - 1], points[i]) > 0) break;
            hull.pop_back(); SZ--;
        }
        hull.push_back(points[i]); SZ++;
    }

    // 볼록 껍질의 모든 변의 길이를 더해서 출력
    double result = 0;
    for (int i = 0; i < SZ - 1; i++) result += dist(hull[i], hull[i + 1]);
    cout << fixed << setprecision(2) << result << '\n'; 
}

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

    int m; cin >> m;
    while (m--) solve();
}

• Python

import sys; input = sys.stdin.readline

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

def dist(a, b):
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

for _ in range(int(input())):
    n = int(input())
    points = sorted(tuple(map(int, input().split())) for _ in range(n))

    # 볼록 껍질의 아래
    hull = []
    for i in range(n):
        while len(hull) > 1:
            if ccw(hull[-2], hull[-1], points[i]) > 0:
                break
            hull.pop()
        hull.append(points[i])

    # 볼록 껍질의 위
    sz = len(hull)
    for i in range(n - 1, -1, -1):
        while len(hull) > sz:
            if ccw(hull[-2], hull[-1], points[i]) > 0:
                break
            hull.pop()
        hull.append(points[i])

    # 볼록 껍질의 모든 변의 길이를 더해서 출력
    print(format(sum(dist(hull[i], hull[i + 1]) for i in range(len(hull) - 1)), '.2f'))