Cod sursa(job #404246)

Utilizator nautilusCohal Alexandru nautilus Data 25 februarie 2010 22:31:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include<fstream.h>
#include<iostream.h>
#define max 120002

double x[max],y[max];
long n,v[max],k,st[max],pas,i;

void coeficienti(double xa,double ya,double xb,double yb,double& aa,double& bb,double& cc)
{ 
 aa=ya-yb;
 bb=xb-xa;
 cc=xa*yb-xb*ya;
}

long semn(double xa,double ya,double xb,double yb,double xc,double yc)
{
 double aa,bb,cc;
 coeficienti(xa,ya,xb,yb,aa,bb,cc);
 if (aa*xc+bb*yc+cc<=0)
	 return -1; else
	 return 1;
}

void modifica()
{
 if (pas==1)
	 {
	  i++;
	  if (i==n)
		  pas=-1;
	 } else
     i--;
}

long divide(long p,long q)
{
 long st=p,dr=q;
 double x2=x[p],y2=y[p];
 
 while (st<dr)
	 {
	  while ((st<dr && y[dr]>y2) || (st<dr && y[dr]==y2 && x[dr]>=x2))
		 dr--;
	  x[st]=x[dr];
	  y[st]=y[dr];
	  while ((st<dr && y[st]<y2) || (st<dr && y[st]==y2 && x[st]<=x2))
		  st++;
	  x[dr]=x[st];
	  y[dr]=y[st];
	 }
 
 x[st]=x2;
 y[st]=y2;
 
 return st;
}

void qsort(long p,long q)
{
 long m=divide(p,q);
 
 if (m-1>p)
	 qsort(p,m-1);
 if (m+1<q)
	 qsort(m+1,q);
}

void acoperire()
{
 qsort(1,n);
 
 pas=1;
 st[1]=1; st[2]=2;
 v[2]=1; k=2; i=2;
 
 while (i>1)
	 {
	  while (v[i])
		  modifica();
	  if (i==0)
		  break;
	  while (k>1 && semn(x[st[k-1]],y[st[k-1]], x[st[k]],y[st[k]], x[i],y[i])==-1)
		  {
		   v[st[k]]=0;
		   k--;
		  }
	  k++;
	  st[k]=i;
	  v[i]=1;
	 }
}

int main()
{
 long i;
	
 ifstream fin("infasuratoare.in");
 fin>>n;
 for (i=1; i<=n; i++)
	 fin>>x[i]>>y[i];
 fin.close();
 
 acoperire();
 
 ofstream fout("infasuratoare.out");
 fout<<k-1<<'\n';
 
 
 fout.setf(ios::fixed);
 fout.precision(6);
 for (i=1; i<=k-1; i++)
	 fout<<x[st[i]]<<" "<<y[st[i]]<<'\n';
 
 fout.close();
 return 0;
}