Cod sursa(job #248336)

Utilizator ilincaSorescu Ilinca ilinca Data 25 ianuarie 2009 14:40:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

#define nmax 120005
#define x first
#define y second

using namespace std;


int n, f=1;
int st [nmax], w [nmax];
vector < pair <double, double> > p (nmax);


void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=1; i <= n; ++i)
	{
		scanf ("%lf%lf", &p [i].x, &p [i].y);
		if ((p [i].y < p [f].y) || (p [i].y == p [f].y && p [i].x < p [f].x))
			f=i;	
	}
	w [++w [0]]=f;
	for (i=1; i <= n; ++i)
		if (i != f)
			w [++w [0]]=i;
}

bool cmp (int i, int j)
{
	return (p [i].y-p [f].y)*(p [j].x-p [f].x) < (p [j].y-p [f].y)*(p [i].x-p [f].x);
}

double ccw (int i, int j, int k)
{
	return (p [k].x-p [i].x)*(p [j].y-p [i].y)-(p [j].x-p [i].x)*(p [k].y-p [i].y);
}

void infasuratoare ()
{
	int i;
	st [++st [0]]=1;
	st [++st [0]]=2;
	for (i=2; i <= n; ++i)
	{
		while (st [0] > 2 && ccw (w [st [st [0]]], w [st [st [0]-1]], w [i]) <= 0)
			--st [0];
		st [++st [0]]=i;
	}
}

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

int main ()
{
	freopen ("infasuratoare.in", "r", stdin);
	freopen ("infasuratoare.out", "w", stdout);
	scan ();
	sort (w+2, w+n+1, cmp);
	infasuratoare ();
	print ();
	return 0;
}