Cod sursa(job #670473)

Utilizator cont_de_testeCont Teste cont_de_teste Data 29 ianuarie 2012 12:10:27
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 100010
#define inf 0x3f3f3f3f
#define ll long long
#define PR pair <int, int>
#define x first
#define y second

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

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;*/
    long long x1 = (ll)A.x, x2 = (ll)B.x;
        long long y1 = (ll)A.y, y2 = (ll)B.y;
        if ( x1*y2==x2*y1 )
            return A<B;
        return x1*y2-x2*y1 > 0;
}

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

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("%d %d", &P[i].x, &P[i].y);
    }
    convex(), v = H.size () - 1;
    /*for (i = 0; i < v; ++i)
        printf ("%d %d\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;
}