Cod sursa(job #1267932)

Utilizator smaraldaSmaranda Dinu smaralda Data 20 noiembrie 2014 14:56:32
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;

#define ITERATOR vector <POINT>::iterator

const double INF = 2e9, eps = 1.e-9;

struct POINT {
    double x, y;

    POINT (double x = 0, double y = 0) {
        this->x = x;
        this->y = y;
    }

    void read() {
        scanf("%lf%lf", &x, &y);
    }
};
vector <POINT> init, p;

void getCoef (POINT P1, POINT P2, double &a, double &b, double &c) {
    a = P1.y - P2.y;
    b = P2.x - P1.x;
    c = P1.x * P2.y - P2.x * P1.y;
}

double ccw (POINT P1, POINT P2, POINT P3) {
    return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}

bool cmp (POINT a, POINT b) {
    return ccw(init[0], a, b) > 0;
}

void convexHull() {
    int i;

    for(i = 1; i < init.size(); ++ i)
        if(init[i].y < init[0].y - eps || (fabs(init[i].y - init[0].y) < eps && init[i].x < init[0].x - eps))
            swap(init[0], init[i]);

    sort(init.begin() + 1, init.end(), cmp);

    i = 0;
    while(i < init.size()) {
        if(p.size() < 2 || ccw(p[p.size() - 2], p[p.size() - 1], init[i]) > 0) {
            p.push_back(init[i]);
            ++ i;
        }
        else
            p.erase(p.end() - 1);
    }
}

double boundingBoxArea () {
    double xmin, xmax, ymin, ymax;

    xmin = ymin = INF;
    xmax = ymax = -INF;
    for(ITERATOR it = p.begin(); it != p.end(); ++ it)
        xmin = min(xmin, it->x),
        xmax = max(xmax, it->x),
        ymin = min(ymin, it->y),
        ymax = max(ymax, it->y);
    return (xmax - xmin) * (ymax - ymin);
}

double distPointLine (POINT P, POINT A, POINT B) {
    double a, b, c;

    getCoef(A, B, a, b, c);
    return fabs(P.x * a + P.y * b + c) / sqrt(a * a + b * b);
}

double dmax (POINT A, double slope, int &ind) {
    POINT B;
    double ans, dPlus, dMinus, dist;
    int i, iPlus, iMinus;

    B = POINT(A.x + 1, A.y + slope);
    ans = 0;
    dPlus = dMinus = -INF;
    iPlus = iMinus = -1;
    for(i = 0; i < p.size(); ++ i) {
        dist = distPointLine(p[i], A, B);
        if(ccw(A, B, p[i]) >= 0) {
            if(dist > dPlus)
                dPlus = dist,
                iPlus = i;
        }
        else {
            if(dist > dMinus)
                dMinus = dist,
                iMinus = i;
        }
    }

    if(dPlus > dMinus)
        ind = iPlus;
    else
        ind = iMinus;

    ans = 0;
    if(iPlus != -1)
        ans += fabs(dPlus);
    if(iMinus != -1)
        ans += fabs(dMinus);
    return ans;
}

int main() {
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);
    int n, i, ind, next, farthest;
    double lat1, lat2, area, slope;

    scanf("%d", &n);
    init.resize(n);
    for(i = 0; i < n; ++ i)
        init[i].read();

    convexHull();

    area = boundingBoxArea();
    for(i = 0; i < p.size(); ++ i) {
        next = (i + 1) % p.size();

        if(fabs(p[i].x - p[next].x) >= eps && fabs(p[i].y - p[next].y) >= eps) {
            slope = (p[next].y - p[i].y) / (p[next].x - p[i].x);
            lat1 = dmax(p[i], slope, farthest);

            slope = (double)-1 / slope;
            lat2 = dmax(p[farthest], slope, ind);

            area = min(area, lat1 * lat2);
        }
    }

    printf("%.2lf\n", area);
    return 0;
}