Cod sursa(job #1249236)

Utilizator DjokValeriu Motroi Djok Data 26 octombrie 2014 18:24:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;

const double EPS=1e-12;

typedef struct lol {
        double x,y;
}troll;

int st[120005],n,i,p,nr;
bool viz[120005];
troll a[120005];

double area(troll a,troll b,troll c) {
       return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

bool cmp(const troll &a,const troll &b) {
     if(a.x==b.x) return a.y<b.y;
     return a.x<b.x;
}

int main()
{
  ifstream cin("infasuratoare.in");
  ofstream cout("infasuratoare.out");

  cin>>n;
  for(i=1;i<=n;++i) cin>>a[i].x>>a[i].y;

  sort(a+1,a+n+1,cmp);

  st[1]=1; st[2]=2; viz[2]=1; nr=2;
  for(i=1,p=1;i>0;i+=p)
  {
    if(!viz[i]) {
                  while(nr>=2 && area(a[st[nr-1]],a[st[nr]],a[i])<EPS)
                  viz[st[nr--]]=0;
                  st[++nr]=i; viz[i]=1;
                }
    if(i==n) p*=-1;
  }

  cout<<nr-1<<'\n';
  cout<<setprecision(7)<<fixed;
  for(i=1;i<nr;++i) cout<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';

 return 0;
}