Cod sursa(job #789262)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 17 septembrie 2012 18:32:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<stdio.h>
#include<algorithm>
#define e 1/1000000000


using namespace std;


struct joe
{double x,y;};


bool less(joe a, joe b)
{
	if(a.y-b.y<0-e)
		return 1;
	if(a.y-b.y>-e&&a.y-b.y<e&&a.x-b.x<-e)
		return 1;
	return 0;
}


joe mi;


double ccw(joe a, joe b, joe c)
{
	return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}



bool comp(joe a, joe b)
{
	double cp=ccw(mi,a,b);
	if(cp>e)
		return 1;
	if(cp<e)
		return 0;
	if((a.x-mi.x)*(a.x-mi.x)+(a.y-mi.y)*(a.y-mi.y)>(b.x-mi.x)*(b.x-mi.x)+(b.y-mi.y)*(b.y-mi.y))
		return 0;
	return 1;
}


joe st[120004];
joe v[120004];



int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	int n,i,p=0;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%lf%lf",&v[i].x,&v[i].y);
		if((mi.x==0&&mi.y==0)||less(v[i], mi))
		{
			mi.x=v[i].x;
			mi.y=v[i].y;
			p=i;
		}
	}
	v[p].x=v[1].x;
	v[p].y=v[1].y;
	v[1].x=mi.x;
	v[1].y=mi.y;
	sort(v+2,v+n+1,comp);
	p=2;
	st[1].x=mi.x;
	st[1].y=mi.y;
	st[2].x=v[2].x;
	st[2].y=v[2].y;
	for(i=3;i<=n;++i)
	{
		if(ccw(st[p-1],st[p],v[i])>e)
		{
			st[++p].x=v[i].x;
			st[p].y=v[i].y;
		}
		else
		{
			p--;
			while(p>1&&ccw(st[p-1],st[p],v[i])<e)
				p--;
			++p;
			st[p].x=v[i].x;
			st[p].y=v[i].y;
		}
	}
	printf("%d\n",p);
	for(i=1;i<=p;++i)
		printf("%lf %lf\n",st[i].x,st[i].y);
	return 0;
}