Cod sursa(job #256641)

Utilizator otilia_sOtilia Stretcu otilia_s Data 11 februarie 2009 23:04:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <stdio.h>
#include <cmath>
#define NMAX 120002
typedef struct punct {double x, y;} Punct;
Punct P[NMAX],S[NMAX];
int n;
double u[NMAX];

void citire()
{ FILE *fin=fopen("infasuratoare.in","r");
 fscanf(fin,"%d",&n);
 int i;
 for (i=0;i<n;i++)
  fscanf(fin,"%lf%lf",&P[i].x,&P[i].y);
 fclose(fin);
}

void pct_st_jos()
{int i;
 for (i=1;i<n;i++)
  if (P[i].y<P[0].y || (abs(P[i].y-P[0].y)<0.0000001&& P[i].x<P[0].x))
     {
      Punct aux=P[i]; P[i]=P[0];P[0]=aux;
     }
}

double dif(double a, double b)
{
 return fabs(a-b);
}

double dist(Punct a, Punct b)
{
 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int pivot(int i, int j)
{ int st,dr,di,dj;
 st=i; dr=j; di=1; dj=0;
 while (st<dr)
  {
   if (u[st]>u[dr]) {Punct aux=P[st]; P[st]=P[dr]; P[dr]=aux;
		     double at=u[st];u[st]=u[dr]; u[dr]=at;
		     di=di^1; dj=dj^1;
		    }
     else
   if (dif(u[st],u[dr])<0.000001)
    if (dist(P[0],P[st])>dist(P[0],P[dr]))
		    {Punct aux=P[st]; P[st]=P[dr]; P[dr]=aux;
		     di=di^1; dj=dj^1;
		    }
   st+=di; dr-=dj;
  }
 return st;
}

void qsort(int st, int Dr)
{
 if (st<Dr) {
	     int p=pivot(st,Dr);
	     qsort(st,p-1);
	     qsort(p+1,Dr);
	    }
}

void polar()
{ int i;
 for (i=1;i<n;i++)
  if (dif(P[i].x,P[0].x)<0.00001&&dif(P[i].y,P[0].y)<0.000001)u[i]=0;
     else u[i]=atan2(P[i].y-P[0].y,P[i].x-P[0].x);
 qsort(1,n-1);
}

double sens(Punct P1, Punct P2, Punct P3)
{
 return ((P2.x-P1.x)*(P3.y-P1.y)-(P3.x-P1.x)*(P2.y-P1.y));
}

int main()
{
 citire();
 pct_st_jos();
 polar();
 int l,i;
 S[0]=P[0]; S[1]=P[1]; l=1;
 for (i=2;i<n;i++)
  {
   double o=sens(S[l-1],S[l],P[i]);
   if (dif(o,0)<0.000001) {S[l]=P[i];}
      else        
       {      
        while(o<=0&&l>1) {l--;o=sens(S[l-1],S[l],P[i]);}
        S[++l]=P[i]; 
       }
  }

  FILE *fout=fopen("infasuratoare.out","w");
  fprintf(fout,"%d\n",l+1);
  for (i=0;i<=l;i++)
   fprintf(fout,"%lf %lf\n",S[i].x,S[i].y);
  fclose(fout);
return 0;
}