Cod sursa(job #2874967)

Utilizator Matei_PanzariuMatei Panzariu Matei_Panzariu Data 20 martie 2022 16:13:10
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct
{
    double x,y;
};
punct v[100002],st[100002],pct;
int n,pos,vf;
double CP(punct a,punct b,punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool sorta(punct a,punct b)
{
    return(CP(v[1],a,b)<0);
}
int main()
{
    cin>>n;
    pct.x=2e9;
    pct.y=2e9;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        if(v[i].y<pct.y)
            pct=v[i],pos=i;
        else
        if(v[i].y==pct.y && v[i].x<pct.x)
           pct=v[i],pos=i;
    }
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,sorta);
    st[vf++]=v[1];
    st[vf]=v[2];
    for(int i=3;i<=n;i++)
    {
        while(vf>=1 && CP(st[vf-1],st[vf],v[i])>0)
            vf--;
        st[++vf]=v[i];
    }
    cout<<vf+1<<'\n';
    while(vf>=0)
    {
        cout<<setprecision(9)<<fixed<<st[vf].x<<' '<<st[vf].y<<'\n';
        vf--;
    }
}