Cod sursa(job #2487148)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 4 noiembrie 2019 02:42:54
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

int n,tp;
struct punct{

    double x,y;

} a[120005];
int st[120005];

int isLeft(const punct &P,const punct &Q,const punct &R){

    return ((Q.x-P.x)*(R.y-P.y)-(Q.y-P.y)*(R.x-P.x)>0);

}

int cmp(const punct &P,const punct &Q){

    return isLeft(a[1],P,Q);

}

int main(){

    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;

    for(int i=2;i<=n;i++)
        if(a[1].x>a[i].x ||
           a[1].x==a[i].x && a[1].y>a[i].y)
                swap(a[1],a[i]);

    sort(a+2,a+n+1,cmp);
    st[1]=1; st[2]=2;
    tp=2;
    for(int i=3;i<=n;i++){

        while(tp>=2 && !isLeft(a[st[tp-1]],a[st[tp]],a[i])) --tp;
        st[++tp]=i;

    }

    cout<<tp<<'\n';
    for(int i=1;i<=tp;i++)
        cout<<fixed<<setprecision(6)<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';

}