Cod sursa(job #862907)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 23 ianuarie 2013 00:24:45
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 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 MAXN 100005
#define INF 1000000000000000.0

struct Point {
    double x, y;
};

int N;
Point P[MAXN];
Point st[MAXN];
int head;

inline 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;
}

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);
}

double distToLine(const Point &A, const Point &B, double panta) {
    if(panta == 0.0)
        return fabs(A.x - B.x);
    if(panta == INF)
        return fabs(A.y - B.y);

    // y = m * x + n
    double m = panta;
    double n = B.y - m * B.x;

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

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

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

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

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

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

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

        st[++head] = P[i];
    }

    N = head + 1;
    for(int i = 0; i < N; i++)
        P[i] = st[i];

    double ans = INF;
    for(int i = 0; i < N; i++) {
        Point A = P[i];
        Point B = P[(i + 1) % N];

        double panta = 0.0;
        if(A.y == B.y)
            panta = INF;
        else
            panta = (A.y - B.y) / (A.x - B.x);

        double perp;
        if(panta == INF)
            perp = 0.0;
        else if(panta == 0.0)
            perp = INF;
        else
            perp = -1.0 / panta;

        int up = i;
        int side1 = i;
        int side2 = i;

        for(int j = 0; j < N; j++) {
            if(distToLine(P[j], A, panta) > distToLine(P[up], A, panta))
                up = j;
            if(distToLine(P[j], A, perp) > distToLine(P[side1], A, perp))
                side1 = j;
        }

        for(int j = 0; j < N; j++)
            if(distToLine(P[j], P[side1], perp) > distToLine(P[side2], P[side1], perp))
                side2 = j;

        double crt = distToLine(P[up], A, panta) * distToLine(P[side1], P[side2], perp);
        ans = min(ans, crt);
    }

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

    return 0;
}