Cod sursa(job #256738)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 12 februarie 2009 06:42:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <stdio.h>

#define MAX 120000
#define INF 1000000000
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

double X[MAX],Y[MAX];
long double V[MAX];
int IND[MAX],ST[MAX];
int PI,N;

long double semn(int,int,int);
void quick(long,long);
long poz(long,long);

int main()
{
 int i;

 fscanf(fin,"%d\n",&N);

 X[0]=INF;
 Y[0]=INF;

 int punct_initial=0;

 for(i=1;i<=N;++i)
 {
  fscanf(fin,"%lf %lf",&X[i],&Y[i]);

  if(X[i]<X[punct_initial] || (X[i]==X[punct_initial] && Y[i]<Y[punct_initial]))
   punct_initial=i;
 }

 fclose(fin);

 PI=punct_initial;

 for(i=1;i<=N;++i)
 {
  if(i==punct_initial)
   continue;
  IND[++IND[0]]=i;
 }

 quick(1,IND[0]);

 ST[ST[0]=1]=punct_initial;

 for(i=1;i<=IND[0];++i)
 {
  if(IND[i]==punct_initial)
   continue;
  while(ST[0]>=2 && semn(ST[ST[0]-1],ST[ST[0]],IND[i]) > 0)
    --ST[0];
  ST[++ST[0]]=IND[i];
 }

 ST[++ST[0]]=punct_initial;

 fprintf(fout,"%d\n",ST[0]-1);

 for(i=ST[0]-1;i>0;i--)
  fprintf(fout,"%lf %lf\n",X[ST[i]],Y[ST[i]]);
 fclose(fout);

 return 0;
}

long double semn(int i,int j,int k)
{
 return (long double) (X[i]*Y[j]+X[j]*Y[k]+X[k]*Y[i])-(Y[i]*X[j]+Y[j]*X[k]+Y[k]*X[i]);
}

void quick(long st,long dr)
{
 if(st<dr)
 {
  long k=poz(st,dr);
  quick(st,k-1);
  quick(k+1,dr);
 }
}

long poz(long st,long dr)
{
 long i=st;
 long j=dr;
 long ii=0;
 long jj=-1;
 long aux;

 while(i<j)
 {
  if((X[IND[i]]-X[PI])*(Y[IND[j]]-Y[PI])>(X[IND[j]]-X[PI])*(Y[IND[i]]-Y[PI]))
  {
   aux=IND[i];
   IND[i]=IND[j];
   IND[j]=aux;

   aux=ii;
   ii=-jj;
   jj=-aux;
  }
  i=i+ii;
  j=j+jj;
 }
return i;
}