Cod sursa(job #306617)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 21 aprilie 2009 17:18:19
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream.h>
double X[120000],Y[120000];
int I,s[119999],N,st[119999],n;
int fc(const void *i, const void *j)
{double x=(double)(X[*(int *)i]-X[I])*(Y[*(int *)j]-Y[I])-(double)(X[*(int *)j]-X[I])*(Y[*(int *)i]-Y[I]);
 if(x>0)return 1;
 if(!x) return 0;
 return -1;}
double unghi(int p1,int p2,int p3)
{return X[p1]*Y[p2]+Y[p1]*X[p3]+X[p2]*Y[p3]-X[p3]*Y[p2]-Y[p1]*X[p2]-X[p1]*Y[p3];}//determinantul cu 3 cele puncte si 1 pe ultima coloana
int main()
{ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>N;
int i=1;
f>>X[0]>>Y[0];
for(;i<N;++i)
{f>>X[i]>>Y[i];
 if(X[i]<X[I]||X[i]==X[I]&&Y[i]<Y[I]) 
  I=i;}
for(i=0;i<I;++i)s[i]=i;
for(i=I;i<N-1;++i)s[i]=i+1;
qsort((void *)s,N-1,sizeof(s[0]),fc);
st[0]=I;
for(i=0;i<N-1;++i)
{while(n&&unghi(st[n-1],st[n],s[i])>0) 
  --n;
 st[++n]=s[i];}
g<<n+1<<'\n';
for(i=n;i>=0;--i)
 g<<X[st[i]]<<' '<<Y[st[i]]<<'\n';
return 0;
}