Cod sursa(job #531631)

Utilizator ilincaSorescu Ilinca ilinca Data 9 februarie 2011 23:26:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define nmax 120005
#define eps (double)1e-12
#define x first
#define y second

using namespace std;

typedef pair <double, double> dd;

int n, st [nmax];
bool v [nmax];
dd p [nmax];


inline double abs (double a)
{
	if (a < 0) 
		return -a;
	return a;
}

inline bool egale (double a, double b)
{
	if (abs (a-b) < eps) return true;
	return false;
}

bool cmp (dd a, dd b)
{
	if (!egale (a.x, b.x))
		return a.x<b.x;
	return a.y<b.y;
}

void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=1; i <= n; ++i)
		scanf ("%lf%lf", &p [i].x, &p [i].y);
	sort (p+1, p+1+n, cmp);
}

inline bool semn (dd p1, dd p2, dd p3)
{
	double a=p1.y-p2.y, b=p2.x-p1.x, c=p1.x*p2.y-p1.y*p2.x;
	double r=a*p3.x+b*p3.y+c;
	//fprintf (stderr, "a=%lf b=%lf c=%lf\n p1.x=%lf p1.y=%lf p2.x=%lf p2.y=%lf p3.x=%lf p3.y=%lf r=%lf\n", a, b, c, p1.x, p1.y, p2.x, p2.y,p3.x, p3.y, r);
	if (r < -eps) return false;
	return true;
}

void convex_hull ()
{
	int i=1, pas=1;
	st [0]=st [1]=1;
	while (!v [1])
	{
		do
		{
			i += pas;
			if (i == n) pas *= -1;
		} while (v [i]);
		//fprintf (stderr, "%d\n" ,i);	
		while (st [0] >= 2 && semn (p [st [st [0]-1]], p [st [st [0]]], p [i]))
			v [st [st [0]--]]=false;
		st [++st [0]]=i;
		v [i]=true;
		//for (int i=1; i <= st [0]; ++i)
		//	fprintf (stderr, "%lf %lf\n", p [st [i]].x, p [st [i]].y);
		//fprintf (stderr, "\n\n\n");
	}
}

void print ()
{
	int i;
	printf ("%d\n", st [0]-1);
	for (i=st [0]-1; i; --i)
		printf ("%lf %lf\n", p [st [i]].x, p [st [i]].y);
}

int main ()
{
	freopen ("infasuratoare.in", "r", stdin);
	freopen ("infasuratoare.out", "w", stdout);
	scan ();
	//for (int i=1; i <= n; ++i)
		//fprintf (stderr, "%lf %lf\n", p [i].x, p [i].y);
	convex_hull ();
	print ();
	return 0;
}