Cod sursa(job #536431)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 18 februarie 2011 17:30:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<stdio.h>
#include<algorithm>
#define E 1e-12

using namespace std;

struct point
{
	double x,y;
};

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

bool Pcmp(point a,point b)
{
	int r=cmp(a.x,b.x);
	if(r==0)return cmp(a.y,b.y)==-1;
	return r==-1;
}

int sgn(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 cmp(A*c.x+B*c.y+C,0);
}



long int n,uz[120001],st[120000],k,nr;
point p[120001],pf[120000];

void create()
{
	st[0]=0;
	st[1]=1;
	k=1;
	int i=2,pas=1;
	uz[1]=1;
	sort(p,p+n,Pcmp);
	
	while(uz[0]==0)
	{
		while(uz[i]>0)
		{
			if(i==n-1)pas=-1;
			i+=pas;
		}
		while(k>=1&&sgn(p[st[k-1]],p[st[k]],p[i])==-1)uz[st[k--]]=0;
		uz[i]=1;
		st[++k]=i;
		
	}
	nr=k;
	for(i=0;i<nr;i++)pf[i]=p[st[i]];
	pf[nr]=p[0];
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%ld\n",&n);
	for(int i=0;i<n;i++) scanf("%lf %lf\n",&p[i].x,&p[i].y);		
	create();
	printf("%ld\n",nr);
	//printf("%lf %lf\n",pf[nr-1].x,pf[nr-1].y);
	for(int i=1;i<nr;i++) printf("%lf %lf\n",pf[i].x,pf[i].y);
	printf("%lf %lf\n",pf[0].x,pf[0].y);
	
}