Cod sursa(job #448213)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 3 mai 2010 10:27:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>
#include <algorithm>
#define per pair<double, double>
#define x first
#define y second
#define MAXN 120010
#define EPS 1e-12

using namespace std;
per a[MAXN];
int st[MAXN];
bool fol[MAXN];
int i,n;

inline int cmp(double a, double b)
{
	if (a+EPS < b) return -1;
	if (b+EPS < a) return 1;
	return 0;
}

inline int det(per a, per b, per c)
{
	return cmp(a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x, 0.0);
}

void Infasuratoare()
{
	int poz, pas;
	sort(a+1,a+n+1);
	memset(fol, false, sizeof(fol));
	st[++st[0]] = 1;
	st[++st[0]] = 2;
	fol[2] = true;
	poz = 3; pas = 1;
	while (!fol[1]){
		while (fol[poz]){
			if (poz == n)
				pas = -1;
			poz +=pas;
		}
		while (st[0]>=2 && det(a[st[st[0]]], a[st[st[0]-1]], a[poz]) == -1){
			fol[st[st[0]]] = false;
			st[0] --;
		}
		st[++st[0]] = poz;
		fol[poz] = true;
	}
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%lf %lf",&a[i].x, &a[i].y);

	Infasuratoare();

	printf("%d\n", st[0]-1);
	for (i=st[0]-1; i; i--)
		printf("%.6lf %.6lf\n", a[st[i]].x, a[st[i]].y);

	return 0;
}