Cod sursa(job #328564)

Utilizator crisojogcristian ojog crisojog Data 2 iulie 2009 15:08:11
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include<stdio.h>
double infinit=1000000001;
struct POINT
{
	float x,y;
}; POINT p[120010],pp,aux,s[120010];
long n,i,poz,k;
void read()
{
	scanf("%ld",&n);
	scanf("%f%f",&p[1].x,&p[1].y);
	pp=p[1];poz=1;
	for(i=2;i<=n;++i)
	{
		scanf("%f%f",&p[i].x,&p[i].y);
		if(pp.y>p[i].y)
			pp=p[i],poz=i;
		else
			if(pp.y==p[i].y)
				if(pp.x>p[i].x)
					pp=p[i],poz=i;
	}
	//--
	aux=p[poz];	p[poz]=p[1]; p[1]=aux;
	//--
}
double ctg(POINT A, POINT B)
{
	if(A.y==B.y) 
		if(B.x-A.x>0) return infinit;
		else return -infinit;
	return ((B.x-A.x)/(B.y-A.y));
}
long part(long st, long dr)
{
	long i,j,m;
	double pivot;
	m=(st+dr)/2;
	pivot=ctg(pp,p[m]);
	i=st-1;j=dr+1;
	while(1)
	{
		do{++i;}while(ctg(pp,p[i])<pivot);
		do{--j;}while(ctg(pp,p[j])>pivot);
		if(i<j)
		{
			aux=p[i];
			p[i]=p[j];
			p[j]=aux;
		}
		else return j;
	}
}
void quicks(long st, long dr)
{
	long pe;
	if(st<dr)
	{
		pe=part(st,dr);
		quicks(st,pe);
		quicks(pe+1,dr);
	}
}
void rev()
{
	for(i=2;i<=(2+n)/2;++i)
	{
		aux=p[i];
		p[i]=p[n-i+2];
		p[n-i+2]=aux;
	}
}
int ccw(POINT a, POINT b, POINT c)
{
	double cp;
	cp=(b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
	if(cp>0) return 1;
	if(cp==0) return 0;
	return -1;
}
void infasuratoare()
{
	s[1]=p[1];
	s[2]=p[2];
	k=2;
	for(i=3;i<=n;++i)
	{
		if(ccw(s[k-1],s[k],p[i])>=0)
			s[++k]=p[i];
		else
		{
			while(ccw(s[k-1],s[k],p[i])<0) k--;
			s[++k]=p[i];
		}
	}
	printf("%ld\n",k);
	for(i=1;i<=k;++i) printf("%f %f\n",s[i].x,s[i].y);
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	read();
	quicks(2,n);
	rev();
	infasuratoare();
	return 0;
}