Cod sursa(job #2054783)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 2 noiembrie 2017 16:03:18
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 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,poz;
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> c,pair<long double,long double> d){
    pair<long double,long double> a,b;
    a=c;
    b=d;
    a.f-=xmin;
    b.f-=xmin;
    a.s-=ymin;
    b.s-=ymin;
    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;
    xmin=1000000001;
    ymin=1000000001;
    for(i=1;i<=n;i++){
        fin>>v[i].f>>v[i].s;
        if(v[i].f<xmin||(v[i].f==xmin&&v[i].s<ymin)){
            xmin=v[i].f;
            ymin=v[i].s;
            poz=i;
        }
    }
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,cmp);
    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;
}