백준 4225번 : 쓰레기 슈트 (C/C++)

<문제>

백준 4225번

 

<참고한 문제>

백준 1708번 : 볼록 껍질

 

<풀이>

직관적으로 생각했을때, 쓰레기의 한쪽면이 쓰레기통의 벽에 닿아있는것이 최선의 경우이다.

오목한면은 해당되지 않음으로 우선 볼록 껍질을 구해준다.

다음 각각의 변에서 가장 거리가 먼 점까지의 거리중 가장 짧은 것을 구해주면 된다.

 

점 (x1, y1) 을 지나는 직선 ax+by+c = 0을 구한다음

점과 직선사이 거리 공식을 적용해주었다.

혹시나 부동 소수점 오차가 날까봐 d를 제곱한 값을 비교해주었다.

 

 

<코드>

#include<bits/stdc++.h>
#define fio()                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0)
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
const double pi = acos(-1);
 
#define x first
#define y second
 
pll p[102];
 
int ccw(pll p1, pll p2, pll p3){
    double tmp = p1.x*p2.y + p2.x*p3.y+p3.x*p1.y - (p2.x*p1.y+p3.x*p2.y+p1.x*p3.y);
    if(tmp > 0.0) return 1;
    else if(tmp == 0.0) return 0;
    else return -1;
}
 
bool compy(pll a, pll b){
    if(a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}
 
bool comp(pll a, pll b){
    int tmp = ccw(p[0], a, b);
    if(tmp != 0) return tmp > 0;
    return a < b;
 
}
 
int main(){
    ll cnt = 0;
    while(1){
        ll n; scanf("%lld", &n);
        if(n == 0) return 0;
        for(int i = 0; i < n; i++){
            scanf("%lf %lf", &p[i].x, &p[i].y);
        }
 
        sort(p, p+n, compy);
        sort(p+1, p+n, comp);
 
        vector<pll> v;
        v.push_back(p[0]);
        v.push_back(p[1]);
        for(int i = 2; i < n; i++){
            while(v.size() >= 2){
                pll p1 = v.back();
                v.pop_back();
                pll p2 = v.back();
 
                if(ccw(p2, p1, p[i]) > 0){
                    v.push_back(p1);
                    break;
                }
            }
            v.push_back(p[i]);
        }
        int vSize = v.size();
        double mi = 200000001;
        for(int i = 0; i < vSize; i++){
 
            double a = v[i].y-v[(i+1)%vSize].y;
            double b = v[(i+1)%vSize].x - v[i].x;
            double c = v[i].y*(v[i].x - v[(i+1)%vSize].x) - v[i].x*(v[i].y - v[(i+1)%vSize].y);
 
            double ma = 0.0;
            for(int j = 0; j < vSize; j++){
                double dd = (a*v[j].x+b*v[j].y+c)*(a*v[j].x+b*v[j].y+c)/(a*a+b*b);
                ma = max(dd, ma);
            }
            mi = min(ma, mi);
        }
        cnt++;
        double ans = sqrt(mi);
        printf("Case %lld: %.2lf\n", cnt, ans+0.005);
    }
}