Cod sursa(job #2528027)

Utilizator PaulDurlaAndronie safafasafs PaulDurla Data 21 ianuarie 2020 12:31:15
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define db double
#define MAXN 120001
#define eps 1e-12

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct points{
    db x,y;
}v[MAXN];
int st[MAXN];
bool ok[MAXN];
bool comp(points a,points b){
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int cmpl(db a,db b){
    if(a+eps<b) return 1;
    if(b+eps<a) return -1;
    return 0;
}
int sign(points a,points b,points c){
    db A,B,C;
    A=a.y-b.y;
    B=b.x-a.x;
    C=a.x*b.y-b.x*a.y;
    return cmpl(A*c.x+B*c.y+C,0);
}
int main(){
    int n;
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,comp);
    /*for(int i=1;i<=n;i++){
        fout<<fixed;
        fout<<setprecision(6);
        fout<<v[i].x<<' '<<v[i].y<<'\n';
    }*/
    int nrst=0,ii,updown,h;
    st[1]=1,st[2]=2;
    ok[2]=1;
    nrst=2;
    ii=3;
    updown=1;
    while(!ok[1]){
        while(ok[ii]){
            if(ii==n) updown=-1;
            ii+=updown;
        }
        while(nrst>=2 and sign(v[st[nrst-1]],v[st[nrst]],v[ii])==-1)
            ok[st[nrst--]]=0;
        nrst++;
        st[nrst]=ii;
        ok[ii]=1;
    }
    h=nrst-1;
    fout<<h<<'\n';
    for(int i=h+1;i>=2;i--){
        fout<<fixed;
        fout<<setprecision(6);
        fout<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
    }
    return 0;
}