Cod sursa(job #1614289)

Utilizator roxana12popescu roxana roxana12 Data 25 februarie 2016 21:29:42
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define eps 1e-12
#define max_n 120050
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct {double x,y;};
punct p[max_n+1],v[max_n+1];
int i,h,n,s[max_n+1],ok[max_n+1];
inline int cmp1 (double a,double b)
{ if(a+eps<b)
   return 1;
   if(b+eps<a)
    return -1;
    return 0;

}
bool cmp (const punct &a, const punct &b)
 { int t;
   t=cmp1(a.x,b.x);
   if(t!=0)
     return t==1;
     return (cmp1(a.y,b.y)==1);

 }
 int semn (punct a, punct b, punct c)
  {
      return cmp1(a.x*b.y+c.x*a.y+b.x*c.y-c.x*b.y-c.y*a.x-a.y*b.x,0);
  }
void rezolva()
{ int k,q;
  sort(v+1,v+n,cmp);
 s[1]=1;
 s[2]=2;
 ok[2]=1;
 k=2;
 i=3;
 q=1;
 while(1)
 { while(ok[i])
   {if(i==n)
     q=-1;
     i=i+q;

   }
     while(k>=2&&semn(v[s[k-1]],v[s[k]],v[i])==-1)
      {ok[s[k]]=0;
      k--;
 }
 s[++k]=i;
 ok[i]=1;
 if(ok[1]==1)
  break;}
h=k-1;
}
int main()
{f>>n;
for(i=1;i<=n;++i)
 f>>v[i].x>>v[i].y;
 rezolva();
 g<<h<<'\n';
 g<<setprecision(6)<<fixed;
 for(i=h;i>=1;--i)
  g<<v[s[i]].x<<' '<<v[s[i]].y<<'\n';
  return 0;

}