Cod sursa(job #37428)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 25 martie 2007 09:27:54
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMAX 1111

struct trie_node { 
	struct trie_node *fiu[2];
} *root, *tnode;

int a[NMAX], b[NMAX], c[NMAX], v[NMAX];
int i, j, k, N, M, xp, yp, nreg, newreg;

int main()
{
	freopen("regiuni.in", "r", stdin);

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

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

	nreg = 0;
	root = (struct trie_node*) malloc(sizeof(struct trie_node));
	root->fiu[0] = root->fiu[1] = NULL;

	for (i = 1; i <= M; i++)
	{
		scanf("%d %d", &xp, &yp);
		
		for (j = 1; j <= N; j++)
		{
			v[j] = a[j] * xp + b[j] * yp + c[j];

			if (v[j] > 0)
				v[j] = 1;
			else
				v[j] = 0;
		}

		// insert into trie

		tnode = root;
		newreg = 0;

		for (j = 1; j <= N; j++)
		{
			if (tnode->fiu[v[j]] == NULL)
			{
				newreg = 1;
				tnode->fiu[v[j]] = (struct trie_node*) malloc(sizeof(struct trie_node));
				tnode->fiu[v[j]]->fiu[0] = tnode->fiu[v[j]]->fiu[1] = NULL;
			}

			tnode = tnode->fiu[v[j]];
		}

		nreg += newreg;
	}

	freopen("regiuni.out", "w", stdout);
	printf("%d\n", nreg);

	return 0;
}