Cod sursa(job #670469)

Utilizator cont_de_testeCont Teste cont_de_teste Data 29 ianuarie 2012 12:02:25
Problema Rubarba Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 100010
#define inf 0x3f3f3f3f
#define db double
#define PR pair <db, db>
#define x first
#define y second

PR P[MAX_N];
int n, i, j;
int v;

inline int check (db A, db B) {
    if (B - A > 0.000001) return -1;
    if (A - B > 0.000001) return  1;
    return 0;
}

bool comp (const PR &A, const PR &B) {
    int X = check (A.x, B.x);
    if (X) return X < 0;
    return check (A.y, B.y) < 0;
}

inline int in (PR A, PR B, PR C) {
    return check ((A.y - B.y) * C.x + (B.x - A.x) * C.y + (A.x * B.y) - (B.x * A.y), 0);
}

vector <int> H;
bool viz[MAX_N];

void convex (void) {
    sort (P + 1, P + n + 1, comp);
    H.push_back (1), H.push_back (2), viz[2] = 1;
    for (int i = 3, wh = 1; viz[1] == 0; H.push_back (i), viz[i] = 1) {
        for (; viz[i] ; i += wh = (i == n ? -1 : wh)) ;
        for (; H.size () > 1 && in (P[*(H.end () - 2)], P[H.back ()], P[i]) < 0; viz[H.back ()] = 0, H.pop_back ());
    }
}

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=1; i<=n; ++i ) {
        scanf("%lf %lf", &P[i].x, &P[i].y);
    }
    convex(), v = H.size () - 1;
    //for (i = 0; i < v; ++i)
       // printf ("%lf %lf\n", P[H[i]].x, P[H[i]].y);
    double INF = 99999999999999999999.0;
    double Aria = INF;

    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 = INF, c12 = -INF, c21 = INF, c22 = -INF;
        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;
}