Cod sursa(job #411788)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 5 martie 2010 10:06:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<cstdio>
#include<algorithm>
#include<bitset>
using namespace std;
#define NM 1200001
#define dd double
const double eps=(double)1e-12;
dd x[NM],y[NM];
int ind[NM],st[NM],N;
bool viz[NM];
struct inf{double x,y;}v[NM];
int compar(dd a,dd b)
{
	if (a+eps<b)
		return -1;
	if (b+eps<a)
		return 1;
	return 0;
}
bool cmp(const inf &a,const inf &b)
{
	int r=compar(a.x,b.x);
	if (r!=0)
		return r==-1;
	r=compar(a.y,b.y);
	return r==-1;
}
int semn(int i, int j, int k)
{
	dd A=v[j].y-v[i].y,B=v[i].x-v[j].x,C=v[j].x*v[i].y-v[i].x*v[j].y;
	return compar(A*v[k].x+B*v[k].y+C,0);
}
void infasuratoare()
{
	viz[2]=1;
	st[++st[0]]=1;
	st[++st[0]]=2;
	int i=3,pas=1;
	while (!viz[1])
	{
		while (viz[i])
		{
			if (i==N)
				pas=-1;
			i+=pas;
		}
		while (st[0]-1 && semn(st[st[0]-1],st[st[0]],i)==-1 )
			viz[st[st[0]--]]=0;
		st[++st[0]]=i;
		viz[i]=1;
	}
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&N);
	int i;
	for (i=1; i<=N; ++i)
	{
		scanf("%lf%lf",&v[i].x,&v[i].y);
	}
	sort(v+1,v+N+1,cmp);
	infasuratoare();
	printf("%d\n",st[0]-1);
	for (i=st[0]-1; i; --i)
		printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
	return 0;
}