Cod sursa(job #37663)

Utilizator gcosminGheorghe Cosmin gcosmin Data 25 martie 2007 11:42:49
Problema Regiuni Scor 80
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 2.9 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) { 
	//	printf("jjjjjjjjjjjjjeeeeeeeeeeeeeeeeeggggggg\n");
		return 0;
	}
*/
	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 (; (smn[j] == 1 || j <= i) && j <= end; j++);
			if (j <= end) { SWAP(pct[i], pct[j]); SWAP(smn[i], smn[j]); }
		}
	}
}


/*
char viz[NMAX];

void get_brute()
{
	int i, j, k, q, w, e, rez = 0;

	for (i = 1; i <= M; i++) {
		if (viz[i]) continue;
//		printf("%d ", i);
		rez++;
		for (j = i + 1; j <= M; j++) {
			e = 1;
			for (k = 1; k <= N && e; k++) {
				q = semn(xx[i], yy[i], a[k], b[k], c[k]);
				w = semn(xx[j], yy[j], a[k], b[k], c[k]);
				if (q != w) e = 0;
			}
			if (e) {
				viz[j] = 1;
//				printf("%d ", j);
			}
		}
//		printf("\n");
	}

	printf("-> %d\n", rez);
}


int aa[NMAX];
int bb[NMAX];
int cc[NMAX];

#include <stdlib.h>

int gen(int N, int M)
{
	freopen("regiuni.in", "w", stdout);

	printf("%d %d\n", N, M);

	int i;

	for (i = 1; i <= N; i++) {
		aa[i] = rand() % 70 - 35;
		bb[i] = rand() % 70 - 35;
		cc[i] = rand() % 6 - 3;
		if (!aa[i] && !bb[i]) { i--; continue; }
		printf("%d %d %d\n", aa[i], bb[i], cc[i]);
	}

	int x, y, e, j;
	for (i = 1; i <= M; i++) {

		while (1) {
			x = rand() % 100 - 50;
			y = rand() % 100 - 50;
			e = 1;
			for (j = 1; j <= N && e; j++) 
				if (semn(x, y, aa[j], bb[j], cc[j]) == 0) e = 0;

			if (e) {
				printf("%d %d\n", x, y);
				break;
			}
		}
	}
fclose(stdout);
return 0;
}
*/
int main()
{
//	srand(666013);
//	gen(1000, 1000);
	
	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);

	}
/*
		for (int jj = 1; jj <= nrg; jj++) {
			for (int ii = beg[jj]; ii <= end[jj]; ii++) printf("%d ", pct[ii]);
			printf("\n");
		}
		printf("-------------\n");
*/


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


//	printf("--------------------------------\n");
//	get_brute();

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