Cod sursa(job #52326)

Utilizator peanutzAndrei Homorodean peanutz Data 18 aprilie 2007 17:36:11
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 1010

int da[NMAX], db[NMAX], dc[NMAX];
int px[NMAX], py[NMAX];
int n, m;
int g[NMAX];
int nr = 1;

void rec(int g[NMAX], int h, int d)
{
	if(d == n)
		return ;

	int g1[NMAX], g2[NMAX];
	int h1, h2;
	int i;
	h1 = h2 = 0;

	for(i = 0; i < h; ++i)
	{
		if(da[d]*px[ g[i] ] + db[d]*py[ g[i] ] + dc[d] > 0)
		{
			g1[h1++] = i;
		}
		else
		{
			g2[h2++] = i;
		}
	}

	if(h1 && h2)
		++nr;

	if(h1)
		rec(g1, h1, d+1);
	if(h2)
		rec(g2, h2, d+1);
}

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

	scanf("%d %d\n", &n, &m);

	for(i = 0; i < n; ++i)
	{
		scanf("%d %d %d\n", &da[i], &db[i], &dc[i]);
	}
	for(i = 0; i < m; ++i)
	{
		scanf("%d %d\n", &px[i], &py[i]);
		g[i] = i;
	}

	rec(g, m, 0);

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

	fclose(stdin);
	fclose(stdout);

	return 0;
}