Cod sursa(job #670462)

Utilizator cont_de_testeCont Teste cont_de_teste Data 29 ianuarie 2012 11:45:07
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX_N 100010
#define inf 0x3f3f3f3f
#define ll long long

struct punct {
    int x, y;
    punct(int a, int b) {
        x=a, y=b;
    }
    punct() {
        x=y=0;
    }
    bool operator<(punct B) {
        return y<B.y || (y==B.y && x<B.x);
    }
} P[MAX_N];
int n, i, j;
int H[MAX_N], v;

struct comp {
    bool operator()(punct A, punct B) {
        long long x1 = (ll)A.x-P[0].x, x2 = (ll)B.x-P[0].x;
        long long y1 = (ll)A.y-P[0].y, y2 = (ll)B.y-P[0].y;
        if ( x1*y2==x2*y1 )
            return A<B;
        return x1*y2-x2*y1 > 0;
    }
};

bool test(punct A, punct B, punct C) {
    long long x1 = (ll)B.x-A.x, x2 = (ll)C.x-A.x;
    long long y1 = (ll)B.y-A.y, y2 = (ll)C.y-A.y;
    return x1*y2 - x2*y1 > 0;
}

void convex() {
    sort(P, P+n, comp());
    H[0] = 0, H[1] = 1, H[2] = 2, v=2;
    for ( i=3; i<n; ++i ) {
        while ( !test(P[H[v-1]], P[H[v]], P[i]) && v>=2 )
            --v;
        H[++v] = i;
    }
    ++v;
}

double myabs(double x) {
    return x<0?-x:x;
}

int main() {
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);

    scanf("%d", &n);
    for ( i=0; i<n; ++i ) {
        scanf("%d %d", &P[i].x, &P[i].y);
    }
    convex();
    /*for (i = 0; i < v; ++i)
        printf ("%d %d\n", P[H[i]].x, P[H[i]].y);*/
    H[v] = H[0];
    double Aria = 1./0;

    for ( i=0; i<v; ++i ) {
        double m1 = (1.*P[H[i+1]].y-P[H[i]].y)/(1.*P[H[i+1]].x-P[H[i]].x);
        double m2 = -1/m1;
        double c11 = 1./0, c12 = -1./0, c21 = 1./0, c22 = -1./0;
        double x, y;
        if ( myabs(m1) < 0.000001 || myabs(m2) < 0.000001 ) {
            for ( j=0; j<v; ++j ) {
                c11 = min(c11, 1.*P[H[j]].x);
                c12 = max(c12, 1.*P[H[j]].x);
                c21 = min(c21, 1.*P[H[j]].y);
                c22 = max(c22, 1.*P[H[j]].y);
            }
            x = c12-c11, y = c22-c21;
        } else {
            for ( j=0; j<v; ++j ) {
                double c1 = P[H[j]].y*1.-m1*P[H[j]].x;
                double c2 = P[H[j]].y*1.-m2*P[H[j]].x;
                c11 = min(c1, c11);
                c12 = max(c1, c12);
                c21	= min(c2, c21);
                c22 = max(c2, c22);
            }
            x = (c12-c11)/sqrt(1+1/(m1*m1));
            y = (c22-c21)/sqrt(1+1/(m2*m2));
        }
        double act = x*y;
        if ( act<Aria ) Aria = act;
    }
    printf("%.2lf\n", Aria);
    return 0;
}