Cod sursa(job #573316)

Utilizator bixcabc abc bixc Data 6 aprilie 2011 10:16:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;

#define Nmax 120010

struct punct {
	double x, y;
} P[Nmax];
	
int n, N;
int Stiva[Nmax], viz[Nmax];

int cmp (const punct &a, const punct &b) {
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

int determ (long double x1, long double y1, long double x2, long double y2, long double x3, long double y3) {
	
	if ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) < 0) return 1;
	return 0;
}

void infasuratoare () {
	
	int i, stp;
	Stiva[++N] = 1;
	Stiva[++N] = 2;
	viz[2] = 1; i = 2; stp = 1;
	
	while (!viz[1]) {
		
		if (i == n) stp = -1;
		i+= stp;
		
		while (viz[i]) {
			if (i == n) stp = -1;
			i+= stp;
		}
		
		while (N > 1 && !determ (P[Stiva[N]].x, P[Stiva[N]].y, P[Stiva[N-1]].x, P[Stiva[N-1]].y, P[i].x, P[i].y))
			viz[Stiva[N--]] = 0;
		
		viz[i] = 1;
		Stiva[++N] = i;
	}
	
	printf ("%d\n", N-1);
	for (i = 1; i < N; i++)
		printf ("%lf %lf\n", P[Stiva[i]].x, P[Stiva[i]].y);
}

int main () {

	freopen ("infasuratoare.in", "r", stdin);
	freopen ("infasuratoare.out", "w", stdout);
	
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf ("%lf %lf", &P[i].x, &P[i].y);
	
	sort (P + 1, P + n + 1, cmp);
	
	infasuratoare ();
	
	return 0;
}