Cod sursa(job #455287)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 13 mai 2010 13:56:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define eps 1e-12

int n,k,st[120005];
short int fol[120005];
struct point 
{
	double x,y;
};
point v[120005];

int compar(double a,double b)
{
	if(a+eps < b) return -1;
	if(b+eps < a) return 1;
	return 0;
}

int cmp(const point& a,const point& b)
{
	if(!compar(a.y,b.y))
		return (compar(a.x,b.x)==-1);
	return (compar(a.y,b.y)==-1);
}

int plan(point A,point B,point C)
{
	double a,b,c;
	a=A.y-B.y;
	b=B.x-A.x;
	c=A.x*B.y-A.y*B.x;
	return (compar(a*C.x+b*C.y+c,0));
}

int main ()
{
	int i;
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lf%lf",&v[i].x,&v[i].y);
	sort(v+1,v+n+1,cmp);	
	k=2;
	st[1]=1;st[2]=2;
	for(i=3;i<=n;i++)
	{
		while(k >= 2 && plan(v[st[k-1]],v[st[k]],v[i])<=0)
			--k;
		st[++k] = i;
	}
	for(i=1;i<=k;i++)
		fol[st[i]]=1;
	fol[1]=0;
	for(i=n;i>=1;i--)
	{
		if(fol[i])
			continue;
		while(k>=2 && plan(v[st[k-1]],v[st[k]],v[i])<=0)
			--k;
		st[++k]=i;
	}	
	printf("%d\n",k-1);
	for(i=1;i<k;i++)
		printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
	return 0;
}