Cod sursa(job #408806)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 3 martie 2010 11:24:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
#include <algorithm>
#define NMAX 120005
using namespace std;
struct pct
{
	double x,y;
};
int n,PI,B[NMAX],r;
pct A[NMAX];
int st[NMAX],t;//stiva
void read()
{
	scanf("%d",&n);
	PI=1;
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%lf%lf",&A[i].x,&A[i].y);
		if (A[i].x<A[PI].x || (A[i].x==A[PI].x && A[i].y<A[PI].y))
			PI=i;
	}
	for (i=1; i<=n; i++)
		if (i!=PI)
			B[++r]=i;
}
bool comp(int i,int j)
{
	return (double)(A[i].x - A[PI].x) * (A[j].y - A[PI].y) < (double)(A[j].x - A[PI].x) * (A[i].y - A[PI].y);
}
long double semn(int i1,int i2,int i3)
{
	return (long double)A[i1].x * A[i2].y + A[i2].x * A[i3].y + A[i3].x * A[i1].y - A[i1].y * A[i2].x - A[i2].y * A[i3].x - A[i3].y * A[i1].x;
}
void infasuratoare()
{
	int i;
	for (i=1; i<=r; i++)
	{
		while (t>=2 && semn(st[t-1],st[t],B[i])>0)
			t--;
		st[++t]=B[i];
	}
	st[++t]=PI;
}
void show()
{
	reverse(st+1,st+t+1);
	int i;
	printf("%d\n",t-1);
	for (i=1; i<t; i++)
		printf("%lf %lf\n",A[st[i]].x,A[st[i]].y);
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	read();
	sort(B+1,B+r+1,comp);
	st[++t]=PI;
	infasuratoare();
	show();
	return 0;
}