Cod sursa(job #441761)

Utilizator ChallengeMurtaza Alexandru Challenge Data 13 aprilie 2010 12:04:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>
#include <algorithm>

const char InFile[]="infasuratoare.in";
const char OutFile[]="infasuratoare.out";
const char RMode[]="r";
const char WMode[]="w";
const double EPS=1e-12;
const int MaxN=120005;

struct POINT 
{
	double x,y;
};

FILE *f;
POINT P[MaxN],H[MaxN];
long int N,HN;

int cmp_lf(double A, double B)
{
	if(A+EPS<B)return -1;
	if(B+EPS<A)return +1;
	return 0;
}

bool cmp_POINT(POINT A,POINT B)
{
	int c=cmp_lf(A.x,B.x);
	if(c!=0)
	{
		return c==-1;
	}
	return cmp_lf(A.y,B.y)==-1;
}

int semn(POINT a,POINT b,POINT c)
{
	double A=a.y-b.y, B=b.x-a.x, C=a.x*b.y-b.x*a.y;
	return cmp_lf(A*c.x+B*c.y+C,0);
}

long int uz[MaxN],st[MaxN];
void ConvexHull()
{
	std::sort(P+1,P+N+1,cmp_POINT);
	int i=3,k=2,pas=1;
	
	uz[2]=1;st[1]=1;st[2]=2;
	while(!uz[1])
	{
 		while(uz[i])
		{
			if(i==N)
			{
				pas=-1;
			}
			i+=pas;
		}
		while(k>=2 && semn(P[st[k-1]],P[st[k]],P[i])==-1)
		{
			uz[st[k--]]=0;
		}
		st[++k]=i;
		uz[i]=1;
	}
	
	HN=k-1;
	for(i=1;i<=HN;++i)
	{
		H[i]=P[st[i]];
	}
}

int main()
{
	f=fopen(InFile,RMode);
	fscanf(f,"%ld",&N);
	for(register int i=1;i<=N;++i)
	{
		fscanf(f,"%lf %lf",&P[i].x,&P[i].y);
	}
	fclose(f);
	
	ConvexHull();
	
	f=fopen(OutFile,WMode);
	fprintf(f,"%ld\n",HN);
	for(register int i=1;i<=HN;++i)
	{
		fprintf(f,"%.6lf %.6lf\n",H[i].x,H[i].y);
	}
	fclose(f);
	return 0;
}