Cod sursa(job #695379)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 28 februarie 2012 12:08:06
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <algorithm>
#define NMAX 120005
#define pdd pair <double,double>
#define x first
#define y second
#define eps 0.000001
using namespace std;
int n,r;
pdd A[NMAX],st[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 A=a.y-b.y;
	double B=b.x-a.x;
	double C=a.x*b.y-b.x*a.y;
	double val=(A*c.x+B*c.y+C);
	return (val<eps);
}
void solve()
{
	int i;
	double a1,b1,c1,val;
	a1=A[1].y-A[n].y;
	b1=A[n].x-A[1].x;
	c1=A[1].x*A[n].y-A[n].x*A[1].y;
	st[++r]=A[1];
	for (i=2; i<n; i++)
	{
		val=a1*A[i].x+b1*A[i].y+c1;
		if (val+eps<0)
		{
			while (r>=2 && semn(st[r-1],st[r],A[i])) r--;
			st[++r]=A[i];
		}
	}
	while (r>=2 && semn(st[r-1],st[r],A[n])) r--;
	st[++r]=A[n];
	
	for (i=n-1; i>1; i--)
	{
		val=a1*A[i].x+b1*A[i].y+c1;
		if (val>eps)
		{
			while (r>=2 && semn(st[r-1],st[r],A[i])) r--;
			st[++r]=A[i];
		}
	}
	printf("%d\n",r);
	for (i=1; i<=r; i++)
		printf("%lf %lf\n",st[i].x,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;
}