Cod sursa(job #1234449)

Utilizator lupuflaviu9lupuflaviu lupuflaviu9 Data 27 septembrie 2014 13:49:07
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <set>
#define NMAX 100005
#define eps 0.000001
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 sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}inline 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(fabs(c)<eps)
return (a.x<b.x);
return (c>0);
}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]);
if(n>1)
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])>=-eps)
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_max,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();

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