Cod sursa(job #536772)

Utilizator ZethpixZethpix Zethpix Data 19 februarie 2011 12:19:07
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <stdio.h>
#include <algorithm>

#define DM 120100
#define Er 0.000000000001

using namespace std;

int S[DM],use[DM];
int i,negativ,ind,N;

struct vector
{
	double x,y;
}v[DM];

inline bool cmp(const vector &a,const vector &b)
{
	if(a.x!=b.x) return a.x<b.x;
	else return a.y<b.y;
}

inline int f(int px,int py,int pz)
{
	double x1,x2,X,y1,y2,Y,a,b,c,E;

	x1=v[px].x;
	x2=v[py].x;
	y1=v[px].y;
	y2=v[py].y;
	X=v[pz].x;
	Y=v[pz].y;

	a=y1-y2;
	b=x2-x1;
	c=x1*y2-x2*y1;

	E=a*X+b*Y+c;

	if(Er+E<0) return -1;
	if(Er<E) return 1;
	return 0;
}

int main()
{
	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);

	//init

	memset(use,0,sizeof(use));
	S[1]=1;
	S[2]=2;
	ind=2;
	use[1]=1;
	use[2]=1;

	//partea ->

	for(i=3;i<=N;i++)
		if(!use[i])
		{
			negativ=f(S[ind-1],S[ind],i);

			while(negativ<0&&ind>1)
			{
				use[S[ind]]=0;
				ind--;
				negativ=f(S[ind-1],S[ind],i);
			}

			ind++;
			S[ind]=i;
			use[i]=1;
		}

	//partea <-

	for(i=N-1;i>0;i--)
		if(!use[i])
		{
			negativ=f(S[ind-1],S[ind],i);

			while(negativ<0&&ind>1)
			{
				use[S[ind]]=0;
				ind--;
				negativ=f(S[ind-1],S[ind],i);
			}

			ind++;
			S[ind]=i;
			use[i]=1;
		}

	printf("%d\n",ind);
	for(i=1;i<=ind;i++)
		printf("%.6lf %.6lf\n",v[S[i]].x,v[S[i]].y);

	return 0;
}