Cod sursa(job #1833645)

Utilizator geo_furduifurdui geo geo_furdui Data 22 decembrie 2016 20:55:30
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <fstream>

using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct bla
{
    float x,y;
} v[150010],aux;
int n,m,st[150100],viz[150101];
bool verif (int poz,bla key)
{
    if(v[poz/2].y<key.y) return true;
    if(v[poz/2].y==key.y)
    {
        if(v[poz/2].x<key.x) return true;
    }
    return false;
}
void climb (int poz)
{
    bla key=v[poz];
    while(3>2)
    {
        if(verif(poz,key) && poz>1)
            v[poz]=v[poz/2],poz/=2;
        else { v[poz]=key; break; }
    }

}
bool verif_again (int fiu,bla key)
{
    if(key.y<v[fiu].y) return true;
    if(key.y==v[fiu].y)
        if(key.x<v[fiu].x) return true;
    return false;
}
void down (int poz)
{
    bla key=v[poz];
    while(3>2)
    {
        int fiu=0;
        if(poz*2<=m) fiu=poz*2;
        if(poz*2+1<=m)
        {
            if(v[fiu].y<v[poz*2+1].y) fiu=poz*2+1;
            else if(v[fiu].y==v[poz*2+1].y && v[fiu].x<v[poz*2+1].x) fiu=poz*2+1;

        }
        if(fiu!=0 && verif_again(fiu,key))
            v[poz]=v[fiu],poz=fiu;
        else { v[poz]=key; break; }
    }
}
void read ()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].x>>v[i].y,climb(i);
        for(int i=n;i>1;i--)
        { m=i-1;
            swap(v[i],v[1]); down(1);
        }
}
bool este_naspa (bla first,bla second,bla cursed_one)
{
    double rez=first.x*second.y;
    rez=rez+second.x*cursed_one.y;
    rez=rez+cursed_one.x*first.y;
    rez=rez-cursed_one.x*second.y;
    rez=rez-first.x*cursed_one.y;
    rez=rez-second.x*first.y;
    if(rez>=0) return true;
    return false;
}
void convex ()
{
    int pi=2,urm=3,unde=1;
    st[1]=1; st[2]=2;
     while(viz[1]==0)
    {
         while(viz[urm]!=0)
         {
             if(urm==n) unde=-1; urm+=unde;
         }
         while(pi>=2 && este_naspa(v[st[pi]],v[st[pi-1]],v[urm]))
            viz[st[pi]]=0,pi--;
         st[++pi]=urm;
         viz[st[pi]]=1;
    } --pi;
    cout<<pi<<"\n";
    for(int i=1;i<=pi;++i)
        cout<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}
int main()
{
    read();
    convex();
    cin.close();
    cout.close();
    return 0;
}