Cod sursa(job #38087)

Utilizator gcosminGheorghe Cosmin gcosmin Data 25 martie 2007 14:41:47
Problema Regiuni Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>

#define NMAX 1010

int N, M;

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

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

int smn[NMAX];

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

inline void SWAP(int &a, int &b)
{
	int 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 <= M; 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;
}