Cod sursa(job #708432)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 6 martie 2012 20:08:31
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 200000;
struct pct {double x; double y;} a[maxn], b[maxn], pi, aux;

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

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 long double produs(pct x, pct y, pct z) {
	return (long double)(y.x - x.x)*(z.y - x.y)-(z.x-x.x)*(y.y-x.y);
}

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

	sort(ind+1, ind+ind[0]+1, comp);
	
	s[s[0] = 1] = ipi;
	
	for (i = 1; i <= ind[0]; ++i) {
		while (s[0] > 1 && produs(a[ s[s[0]-1] ], a[ s[s[0]] ], a[ ind[i] ]) > 0) {
			--s[0];
		}
		s[++s[0]] = ind[i];
	}

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

int main() {
	freopen("terenuri.in", "r", stdin);
	freopen("terenuri.out", "w", stdout);
		pi.y =  1000000000;
		scanf("%ld %ld", &N, &K);
        ipi = 0;
		for (i = 0; i < N; ++i) {
			scanf("%lf %lf", &a[i].x, &a[i].y);
			if (a[i].y < a[ipi].y || (a[i].y == a[ipi].y && a[i].x < a[ipi].x)) {
				ipi = i;
			}
		}
		pi = a[ipi];

		graham();

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


	return 0;
}

void afisare() {
	printf("%ld\n", N);
}