Cod sursa(job #2952204)

Utilizator sims_glAlexandru Simion sims_gl Data 8 decembrie 2022 19:23:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
int i,n,l;
struct punct{
    double x, y;

};
bool semn(punct a, punct b, punct o)
{
    return (a.x-o.x)*(b.y-o.y)<(a.y-o.y)*(b.x-o.x);
}

punct v[150000], st[150000], o ;

int det(punct p1, punct p2, punct p3){

    return (p1.x*p2.y+p1.y*p3.x+p2.x*p3.y- p2.y*p3.x-p1.y*p2.x-p3.y*p1.x)<0;
}


bool comp(punct a, punct b){
    return semn(a, b, v[1]);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    cin>>n;
    int pos=1;
    for(int i=1;i<=n;i++){

        cin>>v[i].x>>v[i].y;

        if(v[i].x<v[pos].x|| (v[i].x==v[pos].x && v[i].y<v[pos].y))
        pos=i;
    }
    swap(v[1], v[pos]);
    sort(v+2, v+n+1, comp);

    st[1]=v[1];
    st[2]=v[2];
    l= 2;
    for(int i=3;i<=n;i++)
    {
        while(l>=2 &&!semn(st[l], v[i], st[l-1]))
        {
            l--;
        }
        st[++l]= v[i];
    }

    cout<<l<<endl;
    cout<<fixed<<setprecision(6)<<st[1].x<<" "<<st[1].y<<endl;
    for(int i=l;i>=2;i--)
    {
        cout<<fixed<<setprecision(6)<<st[i].x<< " "<<st[i].y<<endl;
    }


}