4225번: 쓰레기 슈트 - 최적화 필요

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


빠른답

#include<stdio.h>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pt;
pt p[100], stk[100];
int n, top;
int ccw(pt i, pt j, pt k) {
    return (j.x - i.x)*(k.y - i.y) - (k.x - i.x)*(j.y - i.y);
}
double dis(pt i, pt j, pt k) {
    return abs((i.y - j.y)*k.x - (i.x - j.x)*k.y + i.x*j.y - i.y*j.x)
        / sqrt((i.x - j.x)*(i.x - j.x) + (i.y - j.y)*(i.y - j.y));
}
bool cmp(pt i, pt j) {
    int c = ccw(p[0], i, j);
    return c > 0 || !c && (i.x<j.x || i.x == j.x&&i.y<j.y);
}
int main() {
    for (int c = 1;; c++) {
        scanf("%d", &n);
        if (!n) break;
        for (int i = 0; i < n; i++)
            scanf("%d %d", &p[i].x, &p[i].y);
        swap(p[0], *min_element(p, p + n));
        sort(p + 1, p + n, cmp);
        top = 0;
        for (int i = 0; i < n; i++) {
            while (top > 1 && ccw(stk[top - 2], stk[top - 1], p[i]) <= 0) top--;
            stk[top++] = p[i];
        }
        double res = 2e9;
        for (int i = 0, j = 1; i < top; i++) {
            double l = dis(stk[i], stk[(i + 1) % top], stk[j]);
            while (l < dis(stk[i], stk[(i + 1) % top], stk[(j + 1) % top])) {
                j = (j + 1) % top;
                l = dis(stk[i], stk[(i + 1) % top], stk[j]);
            }
            res = min(res, l);
        }
        printf("Case %d: %.2lf\n", c, res + 0.004);
    }
    return 0;
}