Cod sursa(job #1227839)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 11 septembrie 2014 22:18:04
Problema Rubarba Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define x first
#define y second
#define nMAX 120007
#define Eps 1e-14
#define INF 1e16

using namespace std;

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

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

inline int cmp(pair < double, double > p1, pair < double, double > p2){
    return cp(a[1] , p1 , p2) < 0;
}

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

double dist(const pair < double, double > &A, const pair < double, double > &B){
    return sqrt((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;
    double 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;
    if(panta(a, b) == 0.0)
        return INF;
    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);
        double 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))
                poz = j;
            if(Dist(P[j], A, Perp) > Dist(P[poz1], A, Perp))
                poz1 = j;
        }
        for(int j = 0; j < n; ++j)
            if(Dist(P[j], P[poz1], Perp) > Dist(P[poz2], P[poz1], Perp))
                poz2 = j;
        double crt = Dist(P[poz], A, Panta) * Dist(P[poz1], P[poz2], Perp);
        Ans = min(Ans, crt);
    }
    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();
    for(int i = 0; i < n; ++i)
        a[i] = Stack[i + 1];
    printf("%.2f", solve(a));
    return 0;
}