Cod sursa(job #884250)

Utilizator Rares95Rares Arnautu Rares95 Data 20 februarie 2013 20:07:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
# include <cstdio>
# include <algorithm>
using namespace std;
# define Nmax 120005
# define x first
# define y second

typedef pair<double, double> nod;
nod p[Nmax], stiva[Nmax];
int N, lg;

bool cmp (nod a, nod b)
{
	return ((a.y < b.y) || (a.y == b.y && a.x < b.x));
}
double det(nod a, nod b, nod c)
{
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

void infasuratoare_convexa ()
{
	sort (p + 1, p + N + 1, cmp);
	stiva[1] = p[1];
	stiva[2] = p[2];
	lg = 2;
	for (int i = 3; i <= N; ++i)
	{
		while (det (stiva[lg-1], stiva[lg], p[i]) > 0)
			--lg;
		stiva[++lg] = p[i];
	}
	for (int i = N - 1; i >= 1; --i)
	{
		while (det (stiva[lg-1], stiva[lg], p[i]) > 0)
			--lg;
		stiva[++lg] = p[i];
	}
}

void citire ()
{
	freopen ("infasuratoare.in", "r", stdin);
	scanf ("%d", &N);
	for (int i = 1; i <= N; ++i)
		scanf ("%lf%lf", &p[i].x, &p[i].y);
}

void afisare ()
{
	freopen ("infasuratoare.out", "w", stdout);
	printf ("%d\n", lg - 1);
	for (int i = lg; i >= 2; --i)
		printf ("%.12lf %.12lf\n", stiva[i].x, stiva[i].y);
}

int main ()
{
	citire ();
	infasuratoare_convexa ();
	afisare ();
	return 0;
}