Cod sursa(job #265816)

Utilizator ZillaMathe Bogdan Zilla Data 24 februarie 2009 15:44:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>

#define Nmax 120200
#define inf 10000000

struct p{ double x,y; };

p a[Nmax];

int n,st[Nmax],vf=1;
double minx=inf,miny=inf;

int cmp(p A,p B,p C)
{
	double semn=((A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x));
	if(semn>0) return 1;
	if(semn<0) return -1;
	return 0;
}

void qsort(int st,int dr)
{
	int i=st,j=dr;
	p elem=a[(i+j)/2],aux;
	do
		{
			while(cmp(a[1],a[i],elem) == 1) ++i;
			while(cmp(a[1],elem,a[j]) == 1) --j;
			if(i<=j)
				{
					aux=a[i];
					a[i]=a[j];
					a[j]=aux;
					++i;
					--j;
				}
		}while(i<=j);
	if(st<j)   qsort(st,j);
	if(i<dr)   qsort(i,dr);
}


int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);

	int i;

	scanf("%d",&n);

	for(i=1;i<=n;++i)
		{
			scanf("%lf%lf",&a[i].x,&a[i].y);
			if(a[i].y<miny)
				{
					miny=a[i].y;
					minx=a[i].x;
					a[0]=a[i];
					a[i]=a[1];
					a[1]=a[0];
				}
			else
				if(a[i].y==miny)
					if(a[i].x<minx)
						{
							minx=a[i].x;
							a[0]=a[i];
							a[i]=a[1];
							a[1]=a[0];
						}
		}

/*	for(i=1;i<=n;++i)
		printf("%lf %lf\n",a[i].x,a[i].y);  */
	qsort(2,n);

	st[vf]=1;

	for(i=2;i<=n;++i)
		{
			while(vf>1 && cmp(a[st[vf-1]],a[st[vf]],a[i]) == -1)
				--vf;
			st[++vf]=i;
		}
/*	while(vf>1 && cmp(a[st[vf]],a[st[vf]],a[1]) == -1)
		--vf; */

	printf("%d\n",vf);
	for(i=1;i<=vf;++i)
		{
			printf("%.6f %.6f\n",a[st[i]].x,a[st[i]].y);
		}

	return 0;
}