Cod sursa(job #907198)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 7 martie 2013 18:28:50
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;
 
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

const double eps= 1e-6;
const int nmax= 100000;
const int output_precision= 2;

struct pt{
    double x, y;
};
struct pt_cmp{
    bool operator()(pt x, pt y){
        if (x.x==y.x){
            return x.y<y.y;
        }else{
            return x.x<y.x;
        }
    }
};
pt v[nmax+1];
 
double area(pt x, pt y, pt z){
    return (x.x*y.y+y.x*z.y+z.x*x.y-
        x.x*z.y-y.x*x.y-z.x*y.y)/2;
}
 
int u[nmax+1], l[nmax+1];
pt v_aux[nmax+1];
 
double dist(pt x, pt y){
    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}

double dproj(pt x, pt y, pt z){
    return 2*area(x, y, z)/dist(y, z);
}

pt perp(pt x, pt y, pt z){
    pt aux;
    aux.x= x.x-z.y+y.y;
    aux.y= x.y+z.x-y.x;
    return aux;
}

int n;
inline int next(int x){
    if (x<n){
        return x+1;
    }else{
        return 1;
    }
}

int main(){
    fin>>n;
    if (n<=2){
        fout<<"0.00\n";
        return 0;
    }
    for (int i= 1; i<=n; ++i){
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1, v+n+1, pt_cmp());
     
    u[0]= 1; u[1]= 1;
    l[0]= 1; l[1]= 1;
    for (int i= 2; i<=n; ++i){
        while (u[0]>=2&& area(v[u[u[0]-1]], v[u[u[0]]], v[i])>=eps){
            --u[0];
        }
        ++u[0]; u[u[0]]= i;
        while (l[0]>=2&& area(v[l[l[0]-1]], v[l[l[0]]], v[i])<=-eps){
            --l[0];
        }
        ++l[0]; l[l[0]]= i;
    }
    for (int i= 1; i<=l[0]; ++i){
        v_aux[i]= v[l[i]];
    }
    for (int i= u[0]-1; i>1; --i){
        v_aux[u[0]+l[0]-i]= v[u[i]];
    }
    n= u[0]+l[0]-2;
    for (int i= 1; i<=n; ++i){
        v[i]= v_aux[i];
    }

    int p1= 1, p2= 1, p3= 1;
    pt pt_aux= perp(v[1], v[1], v[2]);
    for (int i= 2; i<=n; ++i){
        if (dproj(v[p2], v[1], v[2])<dproj(v[i], v[1], v[2])+eps){
            p2= i;
        }
        if (dproj(v[p1], v[1], pt_aux)>dproj(v[i], v[1], pt_aux)-eps){
            p1= i;
        }else if (dproj(v[p3], v[1], pt_aux)<dproj(v[i], v[1], pt_aux)+eps){
            p3= i;
        }
    }
    pt_aux= perp(v[p3], v[1], v[2]);
    double sol= -dproj(v[p2], v[1], v[2])*
        dproj(v[p1], v[p3], perp(v[p3], v[1], v[2]));
    
    for (int i= 2; i<=n; ++i){
        int i_n= next(i);
        if (v[i].x==v[i_n].x&& v[i].y==v[i_n].y){
            continue;
        }
        pt_aux= perp(v[i], v[i], v[i_n]);
        
        while (dproj(v[p1], v[i], pt_aux)>dproj(v[next(p1)], v[i], pt_aux)-eps){
            p1= next(p1);
        }
        while (dproj(v[p2], v[i], v[i_n])<dproj(v[next(p2)], v[i], v[i_n])+eps){
            p2= next(p2);
        }
        while (dproj(v[p3], v[i], pt_aux)<dproj(v[next(p3)], v[i], pt_aux)+eps){
            p3= next(p3);
        }
        double sol_aux= -dproj(v[p2], v[i], v[i_n])*
            dproj(v[p1], v[p3], perp(v[p3], v[i], v[i_n]));
        if (sol>sol_aux){
            sol= sol_aux;
        }
    }
    fout<<setprecision(output_precision)<<fixed;
    fout<<sol<<"\n";

    return 0;
}