Cod sursa(job #719453)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 21 martie 2012 20:05:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream>
#include<algorithm>

using namespace std;

int i,n,d,st[120024];

struct point
{
	double x,y;
}p[120024];
	
double isleft(point a,point b,point c)
{
	return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
}

bool comp(point a,point b)
{
	double k=isleft(p[1],a,b);
	if(k>0) return 1;
	return 0;
}

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