Cod sursa(job #418153)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 15 martie 2010 16:08:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct
{
	double x,y;
};
const int N=1<<17;
int u,n,f[N],stiva[N];
punct p[N];
bool comp(const punct &A, const punct &B)
{
	if(A.x>B.x) return false;
	if(A.x<B.x) return true;
	if(A.y>B.y) return false;
	return true;
}
float semn(double x1, double y1, double x2, double y2, double x3, double y3)
{
	return (x1*y2+x2*y3+x3*y1-y2*x3-y3*x1-y1*x2);
}
void convex()
{
	stiva[++u]=1;
	stiva[++u]=2;
	f[1]=f[2]=true;
	for(int i=3;i<=n;i++)
	{
		while(semn(p[stiva[u]].x,p[stiva[u]].y,p[stiva[u-1]].x,p[stiva[u-1]].y,p[i].x,p[i].y)<0 && u>1)
		{
			f[stiva[u]]=false;
			u--;
		}
		if(u==1)
		{
			stiva[++u]=i;
			f[i]=true;
			continue;
		}
		if(semn(p[stiva[u]].x,p[stiva[u]].y,p[stiva[u-1]].x,p[stiva[u-1]].y,p[i].x,p[i].y)>0)
		{
			stiva[++u]=i;
			f[i]=true;
		}
	}
	for(int i=n;i>=1;i--)
		if(f[i]==false || i==1)
		{
			while(semn(p[stiva[u]].x,p[stiva[u]].y,p[stiva[u-1]].x,p[stiva[u-1]].y,p[i].x,p[i].y)<0 && u>1)
			{
				f[stiva[u]]=false;
				u--;
			}
			if(u==1)
			{
				stiva[++u]=i;
				f[i]=true;
				continue;
			}
			if(semn(p[stiva[u]].x,p[stiva[u]].y,p[stiva[u-1]].x,p[stiva[u-1]].y,p[i].x,p[i].y)>0)
			{
				stiva[++u]=i;
				f[i]=true;
			}
		}
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	sort(p+1,p+n+1,comp);
	convex();
	printf("%d\n",u-1);
	for(int i=u-1;i>=1;i--)
		printf("%lf %lf\n",p[stiva[i]].x,p[stiva[i]].y);
	return 0;
}