Cod sursa(job #306624)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 21 aprilie 2009 17:49:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<stdio.h>//fstream afiseaza cu aproximatie
#include<iostream.h>
double X[120000],Y[120000];
int I,s[119999],N,st[119999],n;
int fc(const void *i, const void *j)
{long double x=(long double)(X[*(int *)i]-X[I])*(Y[*(int *)j]-Y[I])-(long double)(X[*(int *)j]-X[I])*(Y[*(int *)i]-Y[I]);
 if(x>0)return 1;
 if(!x) return 0;
 return -1;}
long double unghi(int p1,int p2,int p3)
{return (long double)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()
{FILE *f,*g;
f=fopen("infasuratoare.in","r");
g=fopen("infasuratoare.out","w");
fscanf(f,"%d",&N);
int i=1;
fscanf(f,"%lf %lf",&X[0],&Y[0]);
for(;i<N;++i)
{fscanf(f,"%lf %lf",&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];}
fprintf(g,"%d\n",n+1);
for(i=n;i>=0;--i)
 fprintf(g,"%lf %lf\n",X[st[i]],Y[st[i]]);
fclose(f);
fclose(g);
return 0;
}