Cod sursa(job #1844579)

Utilizator Sanduleac_VladSanduleac Vllad Alexandru Sanduleac_Vlad Data 10 ianuarie 2017 03:45:27
Problema Rubarba Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

#define EPS (1.0E-10)

struct L {
    double x, y;
};

int N;
vector<L> v;
L ll;
vector<L> hull;

/*bool cmp(L l1, L l2) {
    return atan2(ll.y - l1.y, ll.x - l1.x) > atan2(ll.y - l2.y, ll.x - l2.x);
}*/

double ccw(L a, L b, L c) {
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp(L a, L b) {
    return ccw(ll, a, b) > -EPS;
}

double dist(L a, L b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

L norm(L a) {
    L tmp;
    double d = sqrt(a.x * a.x + a.y * a.y);
    tmp = a;
    tmp.x /= d;
    tmp.y /= d;
    return tmp;
}

L rotate(L w, L by) {
    L tmp;
    tmp.x = w.x * by.x + w.y * by.y;
    tmp.y = - w.y * by.x + w.x * by.y;
    return tmp;
}

L subt(L a, L b) {
    L tmp;
    tmp.x = a.x - b.x;
    tmp.y = a.y - b.y;
    return tmp;
}

int main() {
    int i, j;
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);
    scanf("%d", &N);
    if(N <= 2) {
        printf("0.00\n");
        return 0;
    }
    j = 0;
    ll.x = 1.0E10;
    ll.y = 1.0E10;
    for(i = 0; i < N; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        L tmp;
        tmp.x = x;
        tmp.y = y;
        if(tmp.x < ll.x) {
            ll.x = tmp.x;
            ll.y = tmp.y;
            j = i;
        } else if(tmp.x == ll.x && tmp.y < ll.y) {
            ll.x = tmp.x;
            ll.y = tmp.y;
            j = i;
        }
        v.push_back(tmp);
    }
    L tmp = v[0];
    v[0] = v[j];
    v[j] = tmp;
    sort(v.begin() + 1, v.end(), cmp);
    hull.push_back(v[0]);
    hull.push_back(v[1]);
    for(i = 2; i < v.size(); i++) {
        while(hull.size() > 1 && ccw(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) < EPS) {
            hull.pop_back();
        }
        hull.push_back(v[i]);
    }
    double mina = 1.0E15;
    for(i = 0; i < hull.size(); i++) {
        double mx, Mx, my, My;
        L s;
        if(i != 0) {
            s = norm(subt(hull[i - 1], hull[i]));
        } else {
            s = norm(subt(hull[0], hull.back()));
        }
        L crt = rotate(hull[0], s);
        mx = Mx = crt.x;
        my = My = crt.y;
        for(j = 1; j < hull.size(); j++) {
            crt = rotate(hull[j], s);
            if(mx > crt.x) {
                mx = crt.x;
            }
            if(Mx < crt.x) {
                Mx = crt.x;
            }
            if(my > crt.y) {
                my = crt.y;
            }
            if(My < crt.y) {
                My = crt.y;
            }
        }
        if((Mx - mx) * (My - my) < mina) {
            mina = (Mx - mx) * (My - my);
        }
    }
    printf("%.2lf\n", mina);
    return 0;
}