Cod sursa(job #708361)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 6 martie 2012 19:12:05
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 120000;
struct pct {double x; double y;} a[maxn], pi, aux;

long s[maxn], ind[maxn], ipi;
long p, i, N;

bool comp (long i, long j) {
	return (double)(a[i].x - pi.x) * (a[j].y - pi.y) < (double)(a[j].x - pi.x) * (a[i].y - pi.y);
}


inline pct urmatorul_varf(long i) {
	return a[s[p-1]];
}
inline pct varf(long i) {
	return a[s[p]];
}

double produs(pct x, pct y, pct z) {
	return (y.x - x.x)*(z.y - x.y)-(z.x-x.x)*(y.y-x.y);
}
void afisare() {
	printf("%ld\n", N);
	printf("%lf %lf\n", a[0].x, a[0].y);
	for (long i = N-1; i > 0; --i) {
		printf("%lf %lf\n", a[i].x, a[i].y);
	}
}
void graham() {
	sort(ind+1, ind+ind[0]+1, comp);
	
	s[p = 1] = ipi;
	
	for (i = 1; i < N; ++i) {
		while (p > 1 && produs(urmatorul_varf(p), varf(p), a[ind[i]]) > 0) {
			--p;
		}
		s[++p] = ind[i];
	}

	for (i = 0; i < p; ++i) {
		a[i] = a[s[i+1]];
	}
	N = p;
	afisare();
}

int main() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
		pi.y =  1000000000;
		scanf("%ld", &N);

		for (i = 0; i < N; ++i) {
			scanf("%lf %lf", &a[i].x, &a[i].y);
			if (a[i].y < pi.y || (a[i].y == pi.y && a[i].x < pi.x)) {
				pi = a[i];
				ipi = i;
			}
		}

		for (i = 0; i < N; ++i) {
			if (ipi != i) {
				ind[++ind[0]] = i;
			}
		}

		graham();

//		for (i = 0; i < K; ++i) {
//			scanf("%f %f\n", &a[++N].x, &a[N].y);
//			if (a[i].y < pi.y || (a[i].y == pi.y && a[i].x < pi.x)) {
//				pi = a[i];
//			}
//			graham();
//			printf("%ld\n", N);
//		}


	return 0;
}