POJ 3246

3246.cpp

#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

typedef pair<int, int> Pair;

inline int det(Pair p1, Pair p2) {
    return p1.first * p2.second - p1.second * p2.first;
}

inline Pair sub(Pair p1, Pair p2) {
    return Pair(p1.first-p2.first, p1.second-p2.second);
}

int n;
int _n;
int __n;
Pair ps[100001];
Pair _ps[100001];
Pair hull[200002];
Pair _hull[200002];
double ans;
double pos;

int graham(Pair *ps, Pair *hull, int n) {
    int k;
    int _k;

    sort(ps, ps+n);
    k = 0;
    for (int i=0; i<n; i++) {
        while (k > 1 && 
            det(sub(ps[i], hull[k-1]), sub(hull[k-2], hull[k-1])) <= 0) k--;
        hull[k++] = ps[i];
    }
    
    _k = k;
    for (int i=n-2; i>=0; i--) {
        while (k > _k && 
            det(sub(ps[i], hull[k-1]), sub(hull[k-2], hull[k-1])) <= 0) k--;
        hull[k++] = ps[i];
    }
    
    return k-1;
}
    
int main() {
    while (1) {
        scanf("%d", &n);
        if (!n) return 0;

        for (int i=0; i<n; i++) {
            int x, y;
    
            scanf("%d %d", &x, &y);
            ps[i] = Pair(x, y);
        }
    
        _n = graham(ps, hull, n); // n_ <= n^(2/3)
        ans = 10e10;
        for (int i=0; i<_n; i++) {
            int idx = 0;

            for (int j=0; j<n; j++) {
                if (ps[j] != hull[i]) _ps[idx++] = ps[j];
            }

            __n = graham(_ps, _hull, idx);
            pos = 0.0;
            for (int i=1; i<__n-1; i++) {
                pos += abs(det(sub(_hull[i], _hull[0]), sub(_hull[i+1], _hull[0])))/2.0;
            }
            ans = min(ans, pos);
        }

        printf("%.2f\n", ans);
    }
}