Cod sursa(job #795868)

Utilizator radustn92Radu Stancu radustn92 Data 9 octombrie 2012 19:45:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <algorithm>
#define NMAX 120005
#define pdd pair <double,double>
#define x first
#define y second
using namespace std;
int n,r,st[NMAX];
pdd A[NMAX];
bool uz[NMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&A[i].x,&A[i].y);
}
inline int semn(pdd a,pdd b,pdd c)
{
	double a1=a.y-b.y;
	double b1=b.x-a.x;
	double c1=a.x*b.y-b.x*a.y;
	return (a1*c.x+b1*c.y+c1)<0;
}
void solve()
{
	sort(A+1,A+n+1);
	st[++r]=1; st[++r]=2; uz[2]=1;
	int i;
	for (i=3; i<=n; i++)
	{
		while (r>=2 && semn(A[st[r-1]],A[st[r]],A[i]) )
			uz[st[r]]=0,r--;
		st[++r]=i; uz[i]=1;
	}
		
	for (i=n-1; i>=1; i--)
		if (!uz[i])
		{
			while (r>=2 && semn(A[st[r-1]],A[st[r]],A[i]) )
				uz[st[r]]=0,r--;
			st[++r]=i; uz[i]=1;
		}
	r--;
	printf("%d\n",r);
	for (i=1; i<=r; 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(A+1,A+n+1);
	solve();
	return 0;
}