Cod sursa(job #971968)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 10 iulie 2013 17:33:54
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.66 kb
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
#include <utility>

using namespace std;

#define x first
#define y second

typedef pair<double, double> Point;

#define MAXN 100005
int N, a, b;
Point P[MAXN];
Point hull[MAXN];

double dotProduct(const Point &A, const Point &B) {
    return A.x * B.x + A.y * B.y;
}

double crossProduct(const Point &A, const Point &B, const Point &C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

bool cmp(const Point &A, const Point &B) {
    return crossProduct(P[0], A, B) > 0;
}

Point Translate(const Point &A, const Point &B) {
    return Point(B.x - A.x, B.y - A.y);
}

int getNext(int p) {
    return p + 1 < N ? p + 1 : 0;
}

double dist(const Point &A, const Point &B) {
    double dx = A.x - B.x;
    double dy = A.y - B.y;
    return sqrt(dx * dx + dy * dy);
}

// A to B/
double distToLine(const Point &A, const Point &B, double panta) {
    // y = mx + n
    double m = panta;
    double n = B.y - B.x * m;

    Point C;
    C.x = B.x + 1;
    C.y = C.x * m + n;

    double ret = fabs(crossProduct(A, B, C) / dist(B, C));
    return ret;
}

int main() {
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out","w", stdout);

    scanf("%d", &N);

    if(N <= 2) {
        printf("0.00\n");
        return 0;
    }

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &a, &b);
        P[i].x = a;
        P[i].y = b;
    }

    int first = 0;
    for(int i = 1; i < N; i++)
        if(P[first].y > P[i].y)
            first = i;

    swap(P[first], P[0]);
    sort(P + 1, P + N, cmp);

    hull[0] = P[0];
    hull[1] = P[1];
    int sz = 2;

    for(int i = 2; i < N; i++) {
        while(sz >= 2 && crossProduct(hull[sz - 2], hull[sz - 1], P[i]) <= 0)
            sz--;
        hull[sz] = P[i];
        sz++;
    }

//    for(int i = 0; i < sz; i++)
//        printf("%.0lf %.0lf\n", hull[i].x, hull[i].y);

    N = sz;
    int sus = -1;
    int st = -1;
    int dr = 0;
    double dx = -1.0;
    double dy = -1.0;
    double ans = -1.0;
    for(int jos = 0; jos < N; jos++) {
        while(dotProduct(Translate(hull[jos], hull[getNext(jos)]), Translate(hull[dr], hull[getNext(dr)])) > 0)
            dr = getNext(dr);
        if(jos == 0)
            sus = dr;

        while(crossProduct(Point(0, 0), Translate(hull[jos], hull[getNext(jos)]), Translate(hull[sus], hull[getNext(sus)])) > 0)
            sus = getNext(sus);
        if(jos == 0)
            st = sus;

        while(dotProduct(Translate(hull[jos], hull[getNext(jos)]), Translate(hull[st], hull[getNext(st)])) < 0)
            st = getNext(st);

        if(hull[jos].x == hull[getNext(jos)].x) {
            dx = fabs(hull[sus].x - hull[jos].x);
            dy = fabs(hull[dr].y - hull[st].y);
        }
        else if(hull[jos].y == hull[getNext(jos)].y) {
            dy = fabs(hull[sus].y - hull[jos].y);
            dx = fabs(hull[dr].x - hull[st].x);
        }
        else {
            double panta = (hull[getNext(jos)].y - hull[jos].y) / (hull[getNext(jos)].x - hull[jos].x);
            dy = distToLine(hull[sus], hull[jos], panta);

            panta = -1.0 / panta;
            dx = distToLine(hull[st], hull[dr], panta);
        }

        if(jos == 0 || dx * dy < ans)
            ans = dx * dy;
    }

    printf("%.2lf\n", ans);

    return 0;
}