Cod sursa(job #1229400)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 17 septembrie 2014 08:42:24
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define x first
#define y second
#define NMAX 100007
#define INF 1e16
#define EPS 0.01

using namespace std;

pair < double, double > a[NMAX], Stack[NMAX];
int n;

double cp( pair < double , double > A, pair < double , double > B, pair < double , double > C){
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

bool cmp(pair < double, double > A, pair < double, double > B){
    return cp(a[0], A, B) > 0;
}

int infasuratoare(){
    int poz = 0;
    for(int i = 1; i < n; ++i)
        if(a[i] < a[poz])
            poz = i;
    swap(a[0], a[poz]);
    sort(a + 1, a + n, cmp);
    Stack[0] = a[0];
    Stack[1] = a[1];
    int nr = 1;
    for(int i = 2; i < n; ++i){
        while(nr >= 1 && cp(Stack[nr - 1], Stack[nr], a[i]) <= 0)
            --nr;
        Stack[++nr] = a[i];
    }
    return nr + 1;
}

double dist(const pair < double, double > &A, const pair < double, double > &B){
    return (double)sqrt((double)(A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double Dist(const pair < double, double > &A, const pair < double, double > &B, double Panta) {
    if(Panta == INF)
        return fabs(A.y - B.y);
    double m = Panta, n = B.y - m * B.x;
    pair < double, double > C;
    C.x = B.x + 1;
    C.y = m * C.x + n;
    return fabs(cp(A, B, C) / dist(B, C));
}

double panta(pair < double, double> a, pair < double, double> b){
    if(a.x == b.x)
        return INF;
    return (double) (a.y - b.y) / (a.x - b.x);
}

double perp(pair < double, double> a, pair < double, double> b){
    if(panta(a, b) == INF)
        return 0.0;
    return (double) -1.0 / panta(a, b);
}

double solve(pair < double, double > P[]){
    double Ans = INF;
    for(int i = 0; i < n; ++i){
        pair < double, double > A = P[i], B = P[(i + 1) % n];
        double Panta = panta(A, B), Perp = perp(A, B);
        int poz = i, poz1 = i, poz2 = i;
        for(int j = 0; j < n; ++j) {
            if(Dist(P[j], A, Panta) > Dist(P[poz], A, Panta) + EPS)
                poz = j;
            if(Dist(P[j], A, Perp) > Dist(P[poz1], A, Perp) + EPS)
                poz1 = j;
        }
        for(int j = 0; j < n; ++j)
            if(Dist(P[j], P[poz1], Perp) > Dist(P[poz2], P[poz1], Perp) + EPS)
                poz2 = j;
        Ans = min(Ans, Dist(P[poz], A, Panta) * Dist(P[poz1], P[poz2], Perp));
    }
    return Ans;
}

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", &a[i].x, &a[i].y);
    n = infasuratoare();
    memset(a, 0, sizeof(a));
    for(int i = 0; i < n; ++i)
        a[i] = Stack[i];
    printf("%.2f", solve(a));
    return 0;
}