Cod sursa(job #1794752)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 1 noiembrie 2016 18:20:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
# include <fstream>
# include <algorithm>
# include <iomanip>
# include <cmath>
# define DIM 120010
# define f first
# define s second
# define p pair<long double,long double>
# define INF 1000000010
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
p v[DIM],s[DIM],z;
int n,k,i,poz;
long double xm,ym;
long double dist(p a){
    return a.f*a.f+a.s*a.s;
}
long double det(p z,p a,p b){
    return (a.f-z.f)*(b.s-z.s)-(b.f-z.f)*(a.s-z.s);
}
bool cmp(p a,p b){
    if(det(z,a,b)==0)
        return dist(a)<dist(b);
    return det(z,a,b)>0;
}
int main () {
    fin>>n;
    z=make_pair(0,0);
    xm=ym=INF;
    for(i=1;i<=n;i++){
        fin>>v[i].f>>v[i].s;
        if(v[i].s<ym||(v[i].s==ym&&v[i].f<xm)){
            xm=v[i].f;
            ym=v[i].s;
            poz=i;
        }
    }
    swap(v[poz],v[1]);
    for(i=1;i<=n;i++){
        v[i].f-=xm;
        v[i].s-=ym;
    }
    sort(v+2,v+n+1,cmp);
    s[++k]=v[1];
    s[++k]=v[2];
    for(i=3;i<=n;i++){
        while(det(s[k-1],s[k],v[i])<0)
            k--;
        s[++k]=v[i];
    }
    fout<<k<<"\n";
    for(i=1;i<=k;i++)
        fout<<setprecision(6)<<fixed<<s[i].f+xm<<" "<<setprecision(6)<<fixed<<s[i].s+ym<<"\n";
    return 0;
}