Cod sursa(job #39959)

Utilizator gcosminGheorghe Cosmin gcosmin Data 27 martie 2007 10:01:12
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>

#define NMAX 1010

int N, M;

short a[NMAX];
short b[NMAX];
short c[NMAX];
short xx[NMAX];
short yy[NMAX];
short pct[NMAX];

int nrg;
short beg[NMAX];
short end[NMAX];

short smn[NMAX];

inline int semn(int x, int y, int a, int b, int c)
{
	if ((int) x * a + (int) y * b + (int)c < 0) return -1;
	return 1;
}

inline void SWAP(short &a, short &b)
{
	short aux = a;
	a = b;
	b = aux;
}

void desparte(int beg, int end, int a, int b, int c, int gr)
{
	int i, j, nr0 = 0, nr1 = 0, q;

	for (i = beg; i <= end; i++) {
		q = semn(xx[ pct[i] ], yy[ pct[i] ], a, b, c);
		if (q < 0) nr0++;
		else nr1++;
		smn[i] = q;
	}

	if (!nr0 || !nr1) return;

	nrg++;
	::beg[gr] = ::beg[gr];

	::beg[nrg] = ::beg[gr] + nr0;
	::end[nrg] = ::end[gr];

	::end[gr] = ::beg[gr] + nr0 - 1;

	j = 1;
	for (i = beg; i <= end; i++) {
		if (smn[i] == 1) {
			for (; j <= end && (smn[j] == 1 || j <= i); j++);
			if (j <= end) { SWAP(pct[i], pct[j]); SWAP(smn[i], smn[j]); }
		}
	}
}

int main()
{
	int i, j, q;
	
	freopen("regiuni.in", "r", stdin);
	freopen("regiuni.out", "w", stdout);

	scanf("%d %d", &N, &M);

	for (i = 1; i <= N; i++) scanf("%d %d %d", &a[i], &b[i], &c[i]);

	for (i = 1; i <= M; i++) scanf("%d %d", &xx[i], &yy[i]);

	for (i = 1; i <= M; i++) pct[i] = i;

	nrg = 1;
	beg[1] = 1; end[1] = M;

	for (i = 1; i <= N; i++) {
		q = nrg;
		for (j = 1; j <= q; j++) desparte(beg[j], end[j], a[i], b[i], c[i], j);
	}

	printf("%d\n", nrg);

fclose(stdin);
fclose(stdout);
return 0;
}