Cod sursa(job #244665)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 15 ianuarie 2009 18:53:16
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.89 kb
#include <stdio.h>
#include <math.h>

#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define INF 2000000000
#define max 121000

struct puncte
{
 float x;
 float y;
}pct[max],stiva[max],p[max];
double aux[2][max];

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

int n,nr;
int varf,pozz;
int x00=INF,y00=INF;

int graham();
void pune(int);
void elimin();
double produs(int,int,int);
void sort();
double unghi(int);
int poz(int,int);
void quick(int,int);

int main()
{
 int i;
    
 fscanf(fin,"%d",&n);
 for(i=1;i<=n;i++)
 {
  fscanf(fin,"%f %f",&pct[i].x,&pct[i].y);
  
  if (pct[i].y<y00 || (pct[i].y==y00 && pct[i].x<x00))
   x00=pct[i].x,y00=pct[i].y,pozz=i;  
 }
 fclose(fin);
 
 nr=graham();

 fprintf(fout,"%d\n",nr);
 for(i=1;i<=nr;i++)
  fprintf(fout,"%f %f\n",stiva[i].x,stiva[i].y);
 fclose(fout);
  
 return 0;
}         

int graham()
{
 int i;
 double o;
 
 sort();  /// sorteaza in fct de unghiul polar si unde am acelasi unghi in fct de dist cea mai mare
 
 varf=0;
 
 pune(1); /// adauga in stiva pct p[i]   
 pune(2); /// am pus primele 2 pct
 
 for(i=3;i<=n;i++)
 {
  o=produs(varf-1,varf,i);  /// primele 2 din stiva iar restu din p[];          
   if(o==0)
   {
    elimin();  /// elimin pct apropiat
    pune(i);  /// pun pct departat
   }
   else
    if(o>0)  /// la stanga
     pune(i);
    else
    {
     while(o<=0 && varf>1)  /// cat timp se poate si intoarcere la dreapta
     {
      elimin();
      o=produs(varf-1,varf,i);
     }
     pune(i);
    }
 } /// de la for
return varf;                          
}         

void pune(int i)
{       
 varf=varf+1;
 stiva[varf].x=p[i].x;
 stiva[varf].y=p[i].y;
}

void elimin()
{
 varf=varf-1;
}    

double produs(int i,int j,int k)
{
 float x1,y1,x2,y2,x3,y3;

 x1=stiva[i].x;
 y1=stiva[i].y;
 x2=stiva[j].x;
 y2=stiva[j].y;
 x3=p[k].x;
 y3=p[k].y;

 return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
}

void sort()
{
 int i;

 for(i=1;i<=n;i++)
 {
  if(i==pozz)
  {
   aux[0][i]=i;
   aux[1][i]=INF;
   continue;
  }

  aux[0][i]=i;
  aux[1][i]=unghi(i);
 }

 quick(1,n);

 for(i=1;i<=n;i++)
 {
  p[i].x=pct[int (aux[0][n-i+1]) ].x;
  p[i].y=pct[int (aux[0][n-i+1]) ].y;
 }
}

double unghi(int i)
{
 double x,y;

 x=pct[i].x-x00;
 y=sqrt( (pct[i].x-x00)*(pct[i].x-x00) + (pct[i].y-y00)*(pct[i].y-y00) );

 return x/y;
}

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

int poz(int st,int dr)
{
 int auxi;
 double auxii;
 
 int ii=1;
 int jj=0;
 
 while(st<dr)
 {
  if(aux[1][st]>aux[1][dr])
  {
   auxii=aux[1][st];
   aux[1][st]=aux[1][dr];
   aux[1][dr]=auxii;

   auxii=aux[0][st];
   aux[0][st]=aux[0][dr];
   aux[0][dr]=auxii;

   auxi=ii;
   ii=-jj;
   jj=-auxi;
  }
  st+=ii;
  dr+=jj;
 }
 return st;
}