Cod sursa(job #2304085)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 17 decembrie 2018 15:02:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct ura
{
    double a,b;
    int poz;
}v[120003],rez[120003];
double triunghi (int pz1, int pz2, int pz3)
{
    double x1=v[pz1].a,x2=v[pz2].a,x3=v[pz3].a,y1=v[pz1].b,y2=v[pz2].b,y3=v[pz3].b;
    double rez = (x1-x2)*(y1-y3)-(x1-x3)*(y1-y2);
    return rez;
}
int st[120003];
bool cmp (ura a, ura b)
{
    if(a.a<b.a)
        return true;
    if(a.a>b.a)
        return false;
    if(a.b<b.b)
        return true;
    return false;
}
int main()
{
    int n,i,j,k,rezz=0;
    cin>>n;
    for(i=1;i<=n;++i)
    {
        cin>>v[i].a>>v[i].b;
        v[i].poz=i;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;++i)
    {
        rez[i].a=v[i].a;
        rez[i].b=v[i].b;
    }
    k=0;
    st[++k]=1;
    st[++k]=2;
    for(i=3;i<=n;++i)
    {
        while(k>1 && triunghi(st[k-1],st[k],i)<0)
            --k;
        st[++k]=i;
    }
    for(i=1;i<=k;++i)
    {
        rez[++rezz].a=v[st[i]].a;
        rez[rezz].b=v[st[i]].b;
    }
    k=0;
    st[++k]=n;
    st[++k]=n-1;
    for(i=n-2;i>=1;--i)
    {
        while(k>1 && triunghi(st[k-1],st[k],i)<0)
            --k;
        st[++k]=i;
    }
    for(i=2;i<k;++i)
    {
        rez[++rezz].a=v[st[i]].a;
        rez[rezz].b=v[st[i]].b;
    }
    cout<<rezz<<'\n';
    for(i=1;i<=rezz;++i)
        cout<<fixed<<setprecision(6)<<rez[i].a<<' '<<rez[i].b<<'\n';
    return 0;
}