Cod sursa(job #2572547)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 5 martie 2020 13:18:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n,k;
struct point
{
    long double x,y;
};
point v[120005],st[120005];
long double d(point A,point B,point C)
{
    return ((B.y-A.y)*(C.x-A.x)-(B.x-A.x)*(C.y-A.y));
}
bool cmp(point A,point B)
{
    return (d(v[1],A,B)>0);
}
int main()
{
    in>>n;
    int poz=0;
    for(int i=1;i<=n;i++)
    {
        in>>v[i].x>>v[i].y;
        if(poz==0||v[i].x<v[poz].x||(v[i].x==v[poz].x&&v[i].y<v[poz].y)) poz=i;
    }
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,cmp);
    st[1]=v[1];
    st[2]=v[2];
    k=2;

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

    out<<k<<'\n';

    for(int i=k;i>=1;i--)
    {
        out<<fixed<<setprecision(9)<<st[i].x<<" "<<st[i].y<<'\n';
    }
    return 0;
}