Cod sursa(job #407490)

Utilizator BooZZySandu Bogdan BooZZy Data 2 martie 2010 13:07:37
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int viz[120005],st[120005],n,i,b,k,ok;
struct sir
{
	double x;
	double y;
	double tg;
};
sir p[120005],s;
int cmp(sir a,sir b)
{
	if(fabs(a.tg-b.tg)<0.000000000001)
		return a.x<b.x;
	return a.tg<b.tg;
}
void swap(sir &a, sir &b)
{
	sir c;
	c=a;
	a=b;
	b=c;
}
double check(sir a, sir b, sir c)
{
	double s=0;
	s+=a.x*b.y;
	s-=b.y*c.x;		
	s+=a.y*c.x;
	s-=a.x*c.y;
	s+=b.x*c.y;
	s-=a.y*b.x;
	if(s<=0)return 0;
	return 1;
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	s.x=s.y=2000000000;
	for(i=1;i<=n;i++)
	{
		scanf("%lf %lf",&p[i].x,&p[i].y);
		if(p[i].x<s.x||p[i].x==s.x&&p[i].y<s.y){s=p[i];b=i;}
	}
	swap(p[b],p[1]);
	for(i=2;i<=n;i++)
		p[i].tg=(p[i].y-s.y)/(p[i].x-s.x);
	sort(p+2,p+n+1,cmp);
	st[1]=1;st[2]=2;
	k=2;
		for(i=3;i<=n;i++)
		{	
			while(!check(p[st[k-1]],p[st[k]],p[i]))
				k--;
			st[++k]=i;
		}
	printf("%d\n",k);
	for(i=1;i<=k;i++)
		printf("%0.6lf %0.6lf\n",p[st[i]].x,p[st[i]].y);
	return 0;
}