Cod sursa(job #328570)

Utilizator crisojogcristian ojog crisojog Data 2 iulie 2009 15:12:32
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.59 kb
#include<stdio.h>
struct POINT
{
	float x,y;
}; POINT p[120010],aux,sus[120010],jos[120010];
long n,i;

long part1(long st, long dr)
{
	long i,j,m;
	float pivot;
	m=(st+dr)/2;
	pivot=sus[m].x;
	i=st-1;j=dr+1;
	while(1)
	{
		do{++i;} while(sus[i].x<pivot);
		do{--j;} while(sus[j].x>pivot);
		if(i<j)
		{
			aux=sus[i];
			sus[i]=sus[j];
			sus[j]=aux;
		}
		else return j;
	}
}
void quicks1(long st, long dr)
{
	long p;
	if(st<dr)
	{
		p=part1(st,dr);
		quicks1(st,p);
		quicks1(p+1,dr);
	}
	
}
long part2(long st, long dr)
{
	long i,j,m;
	float pivot;
	m=(st+dr)/2;
	pivot=jos[m].x;
	i=st-1;j=dr+1;
	while(1)
	{
		do{++i;} while(jos[i].x<pivot);
		do{--j;} while(jos[j].x>pivot);
		if(i<j)
		{
			aux=jos[i];
			jos[i]=jos[j];
			jos[j]=aux;
		}
		else return j;
	}
}
void quicks2(long st, long dr)
{
	long p;
	if(st<dr)
	{
		p=part2(st,dr);
		quicks2(st,p);
		quicks2(p+1,dr);
	}
	
}
float ccw(POINT p1, POINT p2, POINT p3)
{
	float cp;
	cp=(p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
	return cp;
}
void infasuratoare()
{
	long minx,maxx,j,imin,imax,i,nsus,njos,rem;
	POINT p1,p2,p3;
	//-------------
	minx=p[1].x;maxx=p[1].x;imin=1;imax=1;
	for(i=2;i<=n;++i)
	{
		if(p[i].x<minx)
		{
			minx=p[i].x;
			imin=i;
		}
		else
			if(p[i].x>maxx)
			{
				maxx=p[i].x;
				imax=i;
			}
	}
	//-----------
	nsus=1;njos=1;
	sus[1]=p[imin];jos[1]=p[imin];
	for(i=1;i<=n;++i)
	{
		if(i!=imin && i!=imax)
		{
			if(ccw(p[imin],p[imax],p[i])<0)
			{
				njos++;
				jos[njos]=p[i];
			}
			else
			{
				nsus++;
				sus[nsus]=p[i];
			}
		}
	}
	nsus++;sus[nsus]=p[imax];
	njos++;jos[njos]=p[imax];
	//----------
	quicks1(2,nsus-1);
	quicks2(2,njos-1);
	//----------
	do
	{
		rem=0;i=2;
		while(i<nsus)
		{
			p1=sus[i-1];p2=sus[i];p3=sus[i+1];
			if(ccw(p1,p3,p2)>0) i++;
			else
			{
				rem=1;
				for(j=i;j<=nsus-1;j++)
					sus[j]=sus[j+1];
				nsus--;
			}
		}
	} while(rem);
	//-----------
	do
	{
		rem=0;i=2;
		while(i<njos)
		{
			p1=jos[i-1];p2=jos[i];p3=jos[i+1];
			if(ccw(p1,p3,p2)<0) i++;
			else
			{
				rem=1;
				for(j=i;j<=njos-1;j++)
					jos[j]=jos[j+1];
				njos--;
			}
		}
	} while(rem);
	//--------
	for(i=nsus-1;i>=2;--i)
	{
		njos++;
		jos[njos]=sus[i];
	}
	//--------

	printf("%ld\n",njos);
	for(i=1;i<=njos;++i)
	{
		printf("%f %f\n",jos[i].x,jos[i].y);
	}
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%ld",&n);
	for(i=1;i<=n;++i)
		scanf("%f%f",&p[i].x,&p[i].y);
	infasuratoare();
	return 0;
}