Cod sursa(job #467179)

Utilizator funkydvdIancu David Traian funkydvd Data 28 iunie 2010 12:40:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<cstdio>
#include<algorithm>
#define eps 1e-12
#define pentru(i,a,b) for (int i=a; i<=b; i++)
using namespace std;
int n,k,st[120005];
bool used[120005];
struct pct {double x,y;};
pct 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 pct& a,const pct& b)
{
	if(!compar(a.y,b.y)) return (compar(a.x,b.x)==-1);
	return (compar(a.y,b.y)==-1);
}
int plan(pct A,pct B,pct 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 ()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	pentru(i,1,n) scanf("%lf%lf",&v[i].x,&v[i].y);
	sort(v+1,v+n+1,cmp);	
	k=2; st[1]=1;st[2]=2;
	pentru(i,3,n)
	{
		while(k >= 2 && plan(v[st[k-1]],v[st[k]],v[i])<=0) --k;
		st[++k] = i;
	}
	pentru(i,1,k) used[st[i]]=1;
	used[1]=0;
	for(int i=n;i>=1;i--)
	{
		if(used[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);
	pentru(i,1,k-1) printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
	return 0;
}