[BOJ/Platinum 3] 백준 4225 쓰레기 슈트(C++)

문제 링크

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

4225번: 쓰레기 슈트

 

 

문제

선영이는 쓰레기를 편하게 버리기 위해서 빌딩에 쓰레기 슈트를 만들었다. 쓰레기 슈트는 빌딩에 설치할 수 있는 속이 빈 튜브다. 튜브로 쓰레기를 떨어뜨리면, 쓰레기는 지하실까지 떨어지게 된다.

쓰레기 슈트를 만드는 일은 매우 어려운 일이다. 사람들이 무엇을 버릴지 알 수 없기 때문에, 쓰레기 슈트에 들어가지 않는 쓰레기를 버린다면, 슈트가 막혀버릴 수 있기 때문이다. 쓰레기 슈트를 만드는데 드는 비용은 그 크기에 비례한다. 따라서, 최대한 작게 만드는 것이 효율적이다.

먼저, 쓰레기 슈트를 만드는 문제를 2차원으로 단순화 시켜보자. 슈트는 일정한 너비를 가지고 있고, 다각형으로 모델링된 물체를 이 곳의 상단에 넣을 수 있다.

물체를 넣기 전에, 슈트에 들어갈 수 있게 돌려야 할 수도 있다. 슈트에 던진 이후에는 일직선으로 아래로 떨어지고, 그 동안 물체는 회전하지 않는다.

아래 그림은 물체를 쓰레기 슈트에 들어갈 수 있게 회전시킨 다음 버리는 그림이다.

어떤 물체가 주어진다. 이 물체가 통과할 수 있는 가장 작은 슈트의 너비를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 물체(다각형)의 꼭짓점의 개수 n이 주어진다. (3 ≤ n ≤ 100)

다음 n개 줄에는 꼭짓점의 좌표 xi와 yi가 주어진다. (0 ≤ xi, yi ≤ 104) 꼭짓점은 다각형을 이루는 순서대로 주어진다. 

입력으로 주어지는 다각형의 좌표는 모두 서로 다르며, 다각형의 변은 교차하지 않는다. 엄밀히 따지면, 인접한 변은 한 꼭짓점을 공유한다는 예외가 하나 있다. 물론, 이 경우는 교차하는 것으로 생각하지 않는다.

마지막 테스트 케이스의 다음 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 케이스 번호와 가장 작은 쓰레기 슈트의 너비를 출력한다. 너비는 가장 가까운 0.01의 배수로 올림하여 소수점 둘째 자리까지 출력한다.

예제 입력 1

3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
0

예제 출력 1

Case 1: 2.40
Case 2: 14.15

알고리즘 분류

• 그레이엄 스캔

풀이

그레이엄 스캔을 통해 볼록 껍질을 이루고, 볼록 껍질의 각 변의 점과의 거리의 최대 길이의 최솟값을 구하면 최소의 너비를 가지는 쓰레기 슈트에 쓰레기를 넣을 수 있다.

변과 점 사이의 거리는 변을 이루는 꼭짓점 2개와 점의 외적의 계산 결과에서 변의 길이를 나누어 구한다.

모든 점과의 거리를 비교하여 구할 수 있는 최대의 길이가 바로 해당 변이 가질 수 있는 특정한 점과의 거리의 최댓값이다.

변이 N개 존재한다고 하면 이 N개의 길이 중 최솟값이 구하고자 하는 값이 되는데, 이 값을 소수점 셋째 자리에서 올림한 결과를 정답으로 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define INF 2e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct POINT {
    int X, Y;
};

int N, X, Y, MinX, MinY, First;
int Case = 1;
vector<POINT> Point, CV;
double Answer;

void init() {
    MinX = INF;
    MinY = INF;
    First = 0;
    Point.clear();
    CV.clear();
    Answer = INF;
}

double distance(POINT A, POINT B) {
    return sqrt(((A.X - B.X) * (A.X - B.X)) + ((A.Y - B.Y) * (A.Y - B.Y)));
}

LL CCW(POINT A, POINT B, POINT C) {
    LL OP = ((A.X * B.Y) + (B.X * C.Y) + (C.X * A.Y));
    OP -= ((A.Y * B.X) + (B.Y * C.X) + (C.Y * A.X));
    return OP;
}

bool Comp(POINT A, POINT B) {
    LL NowCCW = CCW(Point[0], A, B);
    if (NowCCW != 0) {
        return (NowCCW > 0);
    }
    if (A.X != B.X) {
        return (A.X < B.X);
    }
    return (A.Y < B.Y);
}

void graham_Scan() {
    for (int i = 0; i < Point.size(); i++) {
        if ((MinX > Point[i].X) || ((MinX == Point[i].X) && (MinY > Point[i].Y))) {
            MinX = Point[i].X;
            MinY = Point[i].Y;
            First = i;
        }
    }
    swap(Point[0], Point[First]);
    sort(Point.begin() + 1, Point.end(), Comp);
    for (int i = 0; i < Point.size(); i++) {
        while ((CV.size() >= 2) && (CCW(CV[CV.size() - 2], CV[CV.size() - 1], Point[i]) <= 0)) {
            CV.pop_back();
        };
        CV.push_back(Point[i]);
    }
}

void calculate() {
    for (int i = 0; i < CV.size(); i++) {
        POINT Prev = CV[i];
        POINT Next = CV[(i + 1) % (int)CV.size()];
        double Distance = distance(Prev, Next);
        double Big = 0;
        for (int j = 0; j < CV.size(); j++) {
            if (((CV[j].X == Prev.X) && (CV[j].Y == Prev.Y)) || ((CV[j].X == Next.X) && (CV[j].Y == Next.Y))) {
                continue;
            }
            LL NowCCW = abs(CCW(Prev, Next, CV[j]));
            double NowD = (double)NowCCW / Distance;
            Big = max(Big, NowD);
        }
        Answer = min(Answer, Big);
    }
    Answer *= 100;
    if (Answer - (LL)Answer > (1e-12)) {
        Answer += 1;
        Answer = (LL)Answer;
    }
    Answer /= 100;
}

void settings() {
    graham_Scan();
    calculate();
}

void find_Answer() {
    cout << "Case " << Case++ << ": ";
    cout << fixed;
    cout.precision(2);
    cout << Answer << "\n";
}

void input() {
    while (1) {
        cin >> N;
        if (N == 0) {
            break;
        }
        init();
        for (int i = 0; i < N; i++) {
            cin >> X >> Y;
            POINT Tmp;
            Tmp.X = X;
            Tmp.Y = Y;
            Point.push_back(Tmp);
        }
        settings();
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}