Cod sursa(job #2054735)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 2 noiembrie 2017 14:54:48
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
# include <fstream>
# include <algorithm>
# include <iomanip>
# define DIM 120010
# define f first
# define s second
using namespace std;
const long double EPS=1e-12;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<long double,long double> v[DIM],rv[DIM];
int s[DIM],n,k,u,i,j,x,y;
long double xmin,ymin;
bool egal(int x){
    return(x>=-EPS&&x<=EPS);
}
long double det(long double X1,long double Y1,long double X2,long double Y2,long double X3,long double Y3){
    return (X2-X1)*(Y3-Y1)-(X3-X1)*(Y2-Y1);
}
bool cmp(pair<long double,long double> a,pair<long double,long double> b){
    if(egal(a.f*b.s-a.s*b.f))
        return (a.f*a.f+a.s*a.s)<(b.f*b.f+b.s*b.s);
    return a.f*b.s>a.s*b.f;
}
int main () {
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i].f>>v[i].s;
        xmin=min(xmin,v[i].f);
        ymin=min(ymin,v[i].s);
    }
    x=int(xmin);
    y=int(ymin);
    for(i=1;i<=n;i++){
        if(x<0)
            v[i].f-=x;
        if(y<0)
            v[i].s-=y;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
        if(x<0)
            v[i].f+=x;
        if(y<0)
            v[i].s+=y;
    }
    rv[++k]=v[n];
    for(i=n;v[i].f*v[i-1].s==v[i].s*v[i-1].f&&i>1;i--)
        rv[++k]=v[i-1];
    for(i=k,j=n;i>=1;i--,j--)
        v[j]=rv[i];
    v[++n]=v[1];
    for(i=1;i<=n;i++){
        while(u>1&&det(v[s[u-1]].f,v[s[u-1]].s,v[s[u]].f,v[s[u]].s,v[i].f,v[i].s)<0)
            u--;
        s[++u]=i;
    }
    fout<<u-1<<"\n";
    for(i=1;i<u;i++)
        fout<<setprecision(6)<<fixed<<v[s[i]].f<<" "<<v[s[i]].s<<"\n";
    return 0;
}