Cod sursa(job #720094)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 22 martie 2012 12:50:34
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include<cstdio>
#include<cmath>
#define abs(x) (x>0)?x:-x
#define inf 1000000001
#define pi 3.1415926
using namespace std;
int n,i,rez;
short c[120002],q,viz[120002];
struct {float x,y;}v[120001];
double unghi(int i,int k)
{
	double x=v[i].x-v[c[q]].x,y=v[i].y-v[c[q]].y;
	if(x==0 && y*k>0)return pi/2;
	if(x==7 && y*k<0)return 3*pi/2;
	if(y==0 && x*k>0)return 0;
	if(y==0 && x*k<0)return pi;
	if(x*k>0 && y*k>0) return atan(y*k/x*k);
	if(x*k>0 && y*k<0) return 3*pi/2+atan(x*k/-y*k);
	if(x*k<0 && y*k>0) return pi-atan(y*k/-x*k);
	if(x*k<0 && y*k<0) return pi+atan(-y*k/-x*k);
	return 0;
}
void infasuratoare()
{int i,j,st,minx=inf,miny=inf,x=0,nr,sf,maxy=-inf,maxx=-inf;
 double val,mind;
  for(i=1;i<=n;i++)
  {
	if( (v[i].y<miny) || (v[i].y==miny && v[i].x<minx)) { st=i; miny=v[i].y; minx=v[i].x; }
	if( (v[i].y>maxy) || (v[i].y==maxy && v[i].x>maxx)) { sf=i; maxy=v[i].y; maxx=v[i].x; }
  }
  c[++q]=st; viz[st]=1;
  while(x!=sf)
  {
	nr=0; mind=inf;
   for(i=1;i<=n;i++)	
	if(!viz[i]) 
	{ 
	 val=unghi(i,1)*180/pi;
	 if(val<mind){ mind=val; x=i; } 
	}
   c[++q]=x;
   viz[x]=1;
  }
  x=c[q];
  while(x!=st)
  {
	nr=0; mind=inf;
   for(i=1;i<=n;i++)	
	if(!viz[i]) 
	{ 
	 val=unghi(i,-1)*180/pi;
	 if(val<mind){ mind=val; x=i; } 
	}
	if(q>1)val=unghi(st,-1)*180/pi;
	 if(val-mind<0){ mind=val; x=st; }
   c[++q]=x;
   viz[x]=1;
  }
  
}

int main()
{
	freopen("infasuratoare.in","r",stdin);freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%f %f",&v[i].x,&v[i].y);
	infasuratoare();
	//printf("%f",dist(1,2,3));
	printf("%d\n",q-1);
	for(i=1;i<q;i++)
		printf("%f %f\n",v[c[i]].x,v[c[i]].y);
return 0;}