Cod sursa(job #557521)

Utilizator cnt_tstcont teste cnt_tst Data 16 martie 2011 18:13:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 120050
#define INF 1 << 30

struct punct {
	double x, y, ctg;
} P[NMAX];

int S[NMAX], N, n, pmin;
double xmin, ymin;

void citire (), infasuratoare (), afisare ();

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

void citire () {
	
	freopen ("infasuratoare.in", "r", stdin);
	
	scanf ("%d", &n);
	
	ymin = INF;
	for (int i = 1; i <= n; i++) {
		scanf ("%lf %lf", &P[i].x, &P[i].y);
		if (P[i].y < ymin)
			ymin = P[i].y, xmin = P[i].x, pmin = i;
	}
}

bool cmp (punct a, punct b) {
	return a.ctg > b.ctg;
}

bool convex (int a, int b, int c) {
	
	double X1 = P[a].x, Y1 = P[a].y, X2 = P[b].x, Y2 = P[b].y, X3 = P[c].x, Y3 = P[c].y;
	
	double A = (X1 - X3) * (Y2 - Y3) - (X2 - X3) * (Y1 - Y3);
	
	if (A > 0) return 1;
	return 0;
}

void infasuratoare () {
	
	swap (P[1], P[pmin]); P[1].x = P[1].y = 0;
	for (int i = 2; i <= n; i++) {
		P[i].x -= xmin, P[i].y -= ymin;
		P[i].ctg = P[i].x / P[i].y;
	}
	
	sort (P + 2, P + 1 + n, cmp);
	
	N = 2, S[1] = 1, S[2] = 2;
	for (int i = 3; i <= n; i++) {
		while (N >= 2 && !convex (S[N-1], S[N], i))
			N--;
		S[++N] = i;
	}
}

void afisare () {
	
	freopen ("infasuratoare.out", "w", stdout);
	
	printf ("%d\n", N);
	
	for (int i = 1; i <= N; i++)
		printf ("%lf %lf\n", P[ S[i] ].x + xmin, P[ S[i] ].y + ymin);
}