Cod sursa(job #385665)

Utilizator cosmyoPaunel Cosmin cosmyo Data 23 ianuarie 2010 11:35:44
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include<fstream.h>
#include<math.h>
struct punct{
	double x;
	double y;
	double d;
	double c;
};
punct a[130000];
long s[130000];
long n,k,vf;
void cit()
{ifstream fin("infasuratoare.in");
  fin>>n;
   long i;
    for(i=1;i<=n;i++)
		fin>>a[i].x>>a[i].y;
 fin.close();
}
void stjos()
{double minx,miny;
  long i;
 minx=a[1].x;
 miny=a[1].y;
 k=1;
  for(i=2;i<=n;i++)
	  if(minx>a[i].x)
	  {miny=a[i].y;
	   minx=a[i].x;
	   k=i;
	  }
	  else
		  if(minx==a[i].x)
			  if(miny>a[i].y)
			  {miny=a[i].y;
	           minx=a[i].x;
	           k=i;
			  }
 a[0].x=a[k].x;
 a[0].y=a[k].y;
 for(i=k+1;i<=n;i++)
	 a[i-1]=a[i];
 n--;
}
ofstream fout("infasuratoare.out");
void calc()
{long i;
 for(i=1;i<=n;i++)
 {a[i].d=sqrt( (a[i].x-a[0].x)*(a[i].x-a[0].x)+ (a[i].y-a[0].y)*(a[i].y-a[0].y) );
  a[i].c=(a[i].x-a[0].x)/a[i].d;
 if(a[i].y<a[0].y)
	 a[i].c++;
 }
}
long cmp(long i,long j)
{if(a[i].c>a[j].c)
	return 1;
else
	if(a[j].c>a[i].c)
		return -1;
else
		if(a[j].c==a[i].c)
		{if(a[i].d>a[j].d)
			return 1;
		else
			return -1;
		}
}

long divide(long st,long dr)
{punct x=a[st];
 a[n+1]=a[st];
 while(st<dr)
 {while(st<dr&&cmp(dr,n+1)<0)
	 dr--;
 a[st]=a[dr];
 while(st<dr&&cmp(st,n+1)>0)
	 st++;
 a[dr]=a[st];
 }
 a[st]=x;
 return st;
}
void quick(int p,int u)
{long m;
 if(p<u)
 {m=divide(p,u);
  quick(p,m-1);
  quick(m+1,u);
 }
}
void elimin()
{long i=1,j,sw;
 double di;
 while(i<n)
 {
	 if(a[i].c==a[i+1].c)
	 {sw=1;
	  di=sqrt((a[i+1].x-a[i].x)*(a[i+1].x-a[i].x)+(a[i+1].y-a[i].y)*(a[i+1].y-a[i].y));
	  if(fabs(a[i+1].d-a[i].d-di)<0.0001) 
	  { for(j=i+1;j<n;j++)
		 a[j]=a[j+1];
	    n--;
	  }
	  else
		  i++;

	 }
	 else
		 i++;
    }  
 }
void stiva()
{long i;
 double x1,y1,x2,y2,x3,y3,de;
 for(i=0;i<=2;i++)
	 s[i]=i;
 vf=2;
 for(i=3;i<=n;i++)
 {x1=a[s[vf-1]].x;
  y1=a[s[vf-1]].y;
  x2=a[s[vf]].x;
  y2=a[s[vf]].y;
  x3=a[i].x;
  y3=a[i].y;
  de=x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1;
 
  while(de<0&&vf>=2)
  {vf--;
  x1=a[s[vf-1]].x;
  y1=a[s[vf-1]].y;
  x2=a[s[vf]].x;
  y2=a[s[vf]].y;
  x3=a[i].x;
  y3=a[i].y;
  de=x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1;
  }
 
  vf++;
  s[vf]=i;
 }
}
void afis()
{ long j,i=0;
  a[0].c=2;
  fout<<vf+1<<'\n';
  for(j=0;j<=vf;j++)
	  fout<<a[s[j]].x<<" "<<a[s[j]].y<<'\n';
 fout.close();
}
int main()
{cit();
 stjos();
 calc();
 quick(1,n);
 elimin();
 stiva();
 afis();
 return 0;
}