Cod sursa(job #350547)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 24 septembrie 2009 17:42:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda info.conc.sept.2 Marime 1.7 kb
#include<fstream>
using namespace std;
int n;
struct punct
{double x,y;
       
       } varf[120004],P[120004];
       int uz[120004],st[1200004],k;
int comp(double v1, double v2)
{if(v1<v2) return +1;
if(v1>v2) return -1;
return 0;
    
    
    }    
int comp_varf(punct v1,punct v2)
{int r=comp(v1.x,v2.x);
    if(r) return r==-1;
 return comp(v1.y,v2.y)==-1;
    
    
    }
int partition(int p,int r)
{punct x=varf[r];
int i=p-1;
for(int j=p;j<r;j++) {if(comp_varf(varf[j],x)==0) {i++;punct aux=varf[i];varf[i]=varf[j];varf[j]=aux;}}
    
punct aux2=varf[i+1];varf[i+1]=varf[r];varf[r]=aux2;
return i+1;    
    
    
    }     
int unghi(punct a,punct b,punct c)
{return ((a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x)>0);
    
    }    
void quicksort(int p,int r)
{if(p<r)
{int q=partition(p,r);
  quicksort(p,q-1);
  quicksort(q+1,r);
        
        
        }
     
     
     }
void ConvexHull()
{quicksort(1,n);
int pas=+1;
uz[1]=0;uz[2]=1;st[1]=1;st[2]=2;k=2;int i=3;
while(!uz[1])
 {
 while(uz[i])
  {if(i==n) pas=-1;
  i+=pas;
             
             }
  while(k>=2 && unghi(varf[st[k-1]],varf[st[k]],varf[i])==0 )
    uz[st[k--]]=0;
  st[++k]=i;uz[i]=1;  
             
             
             }
             
 for(int i=1;i<=k-1;i++)
  P[i]=varf[st[i]];
  P[k]=P[1];    
     
     }
     
     
                
int main()
{freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);


scanf("%d",&n);
for(int i=1;i<=n;i++)
 scanf("%lf %lf",&varf[i].x,&varf[i].y);
 
ConvexHull();
 
 printf("%d \n",k-1);
 for(int i=2;i<=k;i++)
  printf("%.6lf %.6lf \n",P[i].x,P[i].y);  
    
    
    return 0;}