Cod sursa(job #1916858)

Utilizator geo_furduifurdui geo geo_furdui Data 9 martie 2017 10:32:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
int n;
int st[120010],vf;
int used[120010];
struct bla
{
      double x,y;
} date[150010];
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);
}
bool ec_dreptei (int one,int two,int three)
{
      bla a=date[one],b=date[two],c=date[three];
      double r=(c.x-a.x)*(a.y-b.y)-(a.x-b.x)*(c.y-a.y);
      if(r<0) return true;
      return false;
}
void convex ()
{
      int next=3,dir=1;
      st[++vf]=1;
      st[++vf]=2;
      used[2]=1;
      while(used[1]==0)
      {
            while(used[next]!=0)
            {
                  if(next==n) dir=-1;
                  next+=dir;
            }
            while(vf>1 && ec_dreptei(st[vf-1],st[vf],next)) used[st[vf--]]=0;
            st[++vf]=next;
            used[next]=1;
      }
}
void write ()
{
      cout<<vf-1<<"\n";
      for(int i=1;i<vf;i++)
            cout<<fixed<<setprecision(12)<<date[st[i]].x<<" "<<date[st[i]].y<<"\n";
}
int main()
{
    read();
    convex();
    write();
    cin.close();
    cout.close();
    return 0;
}