Cod sursa(job #1906929)

Utilizator geralt_of_riviajohn nathalis geralt_of_rivia Data 6 martie 2017 17:01:09
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include<algorithm>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
int n,vf;
int st[120010];
int used[120010];
struct bla
{
    double x,y;
} date[120010];
bool sortare (bla q,bla w)
{
    if(q.x==w.x) return q.y<w.y;
    return q.x<w.x;
}
void read ()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>date[i].x>>date[i].y;
        sort(date+1,date+n+1,sortare);
}
int ec_dreptei (bla a,bla b,bla c)
{
    return  (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
void convex ()
{
    vf=2;
    st[1]=1; st[2]=2;
    int next=3,dir=1;
    used[2]=1;
    while(used[1]==0)
    {
         while(used[next]!=0)
         {
             if(next==n) dir=-1;
             next+=dir;
         }
         while(vf>1 && ec_dreptei(date[st[vf-1]],date[st[vf]],date[next])<0) used[st[vf--]]=0;
         st[++vf]=next;
         used[next]=1;
    }
}
void write ()
{
    cout<<vf-1<<"\n";
    for(int i=1;i<vf;++i)
        cout<<date[st[i]].x<<" "<<date[st[i]].y<<"\n";
}
int main()
{
    read();
    convex();
    write();
    cin.close();
    cout.close();
    return 0;
}