Cod sursa(job #536432)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 18 februarie 2011 17:30:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 120010
#define err 1e-12
#define x first
#define y second
#define pdd pair<double,double>

using namespace std;

pair<double,double> pct[NMAX],sol[NMAX];
int n,i,stack[NMAX],MIN;
bool used[NMAX];

inline int cmp(double aa, double bb)
{
	if(aa+err<bb) return -1;
	if(bb+err<aa) return 1;
	
	return 0;
}

inline int cmppdd(const pdd &a, const pdd &b)
{
	int v=cmp(a.x,b.x);
	
	if(v) return (v==-1);
	return (cmp(a.y,b.y)==-1);
}

inline int semn(pdd a, pdd b, pdd c)
{
	double aa=a.y - b.y, bb=b.x - a.x, cc=a.x*b.y - a.y*b.x;
	
	return cmp(aa*c.x+bb*c.y+cc,0);
}

inline void pol()
{
	int sens=1,nr_puncte=2;
	
	stack[1] = 1; stack[2] = 2; used[2]= true;
	i=3;
	
	while(!used[1])
	{
		while(used[i])
		{
			if(i==n) sens = -sens;
			i+= sens;
		}
		
		while(nr_puncte>=2 && semn(pct[stack[nr_puncte-1]], pct[stack[nr_puncte]], pct[i])==-1)
			used[stack[nr_puncte--]] = false;
		
		stack[++nr_puncte]=i;
		used[i]=true;
	}
	
	MIN=nr_puncte-1;
	for(i=1;i<=MIN;i++) sol[i]=pct[stack[i]];
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%lf %lf",&pct[i].x,&pct[i].y);
	
	sort(pct+1,pct+n+1,cmppdd);
	pol();
	
	printf("%d\n",MIN);
	for(i=1;i<=MIN;i++)
		printf("%.6lf %.6lf\n",sol[i].x,sol[i].y);
	
	return 0;
}