Cod sursa(job #1228865)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 15 septembrie 2014 18:26:31
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <set>

#define NMAX 100005
#define eps 0.000001l
#define double long double
using namespace std;

int n;
struct punct
{
    double x,y;

    punct(double x=0,double y=0): x(x), y(y) {}
}v[NMAX];

inline double dist(const punct &a,const punct &b){
    return sqrtl((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double ccw(const punct &a,const punct &b,const punct &c){
    return ((a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x));
}

bool operator<(const punct &a,const punct &b){
    double c=ccw(a,v[1],b);

    if(fabsl(c)<eps)
        return (a.y<b.y);
    return (c>=eps);
}

inline void graham_scan(){
    int poz=1;
    for(int i=2;i<=n;i++)
        if(v[i].x<v[poz].x)
            poz=i;
        else if(v[i].x==v[poz].x)
            if(v[i].y<v[poz].y)
                poz=i;

    swap(v[1],v[poz]);
    sort(v+2,v+n+1);

    punct stiva[NMAX];
    poz=0;

    for(int i=1;i<=n;i++){
        while(poz>1 && ccw(stiva[poz-1],stiva[poz],v[i])>=0)
            poz--;

        stiva[++poz]=v[i];
    }

    for(int i=1;i<=poz;i++)
        v[i]=stiva[i];
    n=poz;
}

inline double precalc_bounding_box(){
    double x_min=v[1].x,y_min=v[1].y;
    double x_max=v[1].x,y_max=v[1].y;

    for(int i=2;i<=n;i++){
        x_min=min(x_min,v[i].x);
        y_min=min(y_min,v[i].y);
        x_max=max(x_max,v[i].x);
        y_max=max(y_min,v[i].y);
    }

    return (x_max-x_min)*(y_max-y_min);
}

double dist(double m,int i,int j){
    double b=dist(v[i],punct(0,v[i].y-m*v[i].x));
    double a=ccw(v[j],v[i],punct(0,v[i].y-m*v[i].x));

    a/=b;
    if(a<0)
        a*=(-1);

    return a;
}

double dmax(double m){
    int p_min=1,p_max=1;

    double y1,y2;
    for(int i=1;i<=n;i++){
        y1=v[i].y-m*v[i].x;
        y2=v[p_min].y-m*v[p_min].x;

        if(y1<y2)
            p_min=i;

        y2=v[p_max].y-m*v[p_max].x;
        if(y1>y2)
            p_max=i;
    }

    return dist(m,p_min,p_max);
}

ofstream cout("rubarba.out");
inline void calculate(){
    double ans=precalc_bounding_box();
    //cout<<ans<<endl;

    double curent;
    for(int i=1;i<=n;i++)
        if(v[i].x!=v[i%n+1].x && v[i].y!=v[i%n+1].y){
            curent=dmax((v[i].y-v[i%n+1].y)/(v[i].x-v[i%n+1].x))*dmax(-(v[i].x-v[i%n+1].x)/(v[i].y-v[i%n+1].y));

            if(curent<ans)
                ans=curent;
        }


    cout<<fixed<<setprecision(2)<<ans<<'\n';
}

set<pair<int,int> > toate;

int main()
{
    ifstream cin("rubarba.in");

    cin>>n;
    int p=0;

    for(int i=1;i<=n;i++){
        ++p;
        cin>>v[p].x>>v[p].y;
        v[p].x++;v[p].y++;

        if(toate.count(make_pair(v[p].x,v[p].y)))
            p--;
        else
            toate.insert(make_pair(v[p].x,v[p].y));
    }
    n=p;

    graham_scan();
    //cout<<n<<endl;
    //for(int i=1;i<=n;i++)
    //    cout<<v[i].x<<' '<<v[i].y<<endl;

    calculate();

    cin.close();
    cout.close();
    return 0;
}