Cod sursa(job #670485)

Utilizator SpiderManSimoiu Robert SpiderMan Data 29 ianuarie 2012 12:29:46
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
# include <algorithm>
# include <cstdio>
# include <cmath>
# include <vector>
using namespace std;

# define x first
# define y second

typedef long long ll;
typedef pair <int, int> VR;
const char *FIN = "rubarba.in", *FOU = "rubarba.out";
const int MAX = 100010;

VR V[MAX];
int N, sz;

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

bool comp (const VR &A, const VR &B) {
    if (1LL * A.x * B.y == 1LL * B.x * A.y)
        return A < B;
    return 1LL * A.x * B.y > 1LL * B.x * A.y;
}

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

vector <int> stk;
bool viz[MAX];

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

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d", &N);
    for (int i = 1; i <= N; ++i)
        scanf ("%d %d", &V[i].x, &V[i].y);
    convex_hull (), sz = stk.size () - 1;

    double oo = 99999999999999999999.0, sol = oo;
    for (int i = 0; i < sz; ++i) {
        double pant1 = (1.0 * V[stk[i + 1]].y - V[stk[i]].y) / (1.0 * V[stk[i + 1]].x - V[stk[i]].x), pant2 = -1 / pant1;
        if (fabs (pant1) < 0.000001 || fabs (pant2) < 0.000001) {
            double min1 = oo, min2 = oo, max1 = -oo, max2 = -oo;
            for (int j = 0; j < sz; ++j) {
                min1 = min (min1, 1.0 * V[stk[j]].x);
                min2 = min (min2, 1.0 * V[stk[j]].y);
                max1 = max (max1, 1.0 * V[stk[j]].x);
                max2 = max (max2, 1.0 * V[stk[j]].y);
            }
            sol = min (sol, (max1 - min1) * (max2 - min2));
        } else {
            double min1 = oo, min2 = oo, max1 = -oo, max2 = -oo;
            for (int j = 0; j < sz; ++j) {
                min1 = min (min1, 1.0 * V[stk[j]].y - pant1 * V[stk[j]].x);
                min2 = min (min2, 1.0 * V[stk[j]].y - pant2 * V[stk[j]].x);
                max1 = max (max1, 1.0 * V[stk[j]].y - pant1 * V[stk[j]].x);
                max2 = max (max2, 1.0 * V[stk[j]].y - pant2 * V[stk[j]].x);
            }
            sol = min (sol, ((max1 - min1) / sqrt (1 + 1 / (pant1 * pant1))) * ((max2 - min2) / sqrt (1 + 1 / (pant2 * pant2))));
        }
    }
    fprintf (fopen (FOU, "w"), "%.2lf", sol);
}