Cod sursa(job #1277324)

Utilizator lokixdSebastian lokixd Data 27 noiembrie 2014 15:52:57
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
 
#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';
}
 
int main()
{
    ifstream cin("rubarba.in");
 
    cin>>n;
 
    for(int i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
        v[i].x++;v[i].y++;
    }
 
    graham_scan();
    calculate();
 
    cin.close();
    cout.close();
    return 0;
}