Cod sursa(job #37447)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 25 martie 2007 09:46:38
Problema Regiuni Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.09 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <time.h>

#define NMAX 1111
#define MAX_NODES 1001000

int fiu[MAX_NODES][2], nextnode, 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;
	fiu[0][0] = fiu[0][1] = 0;
	nextnode = 1;

	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 = 0;
		newreg = 0;

		for (j = 1; j <= N; j++)
		{
			if (!fiu[tnode][v[j]])
			{
				newreg = 1;
				fiu[tnode][v[j]] = nextnode;
				fiu[nextnode][0] = fiu[nextnode][1] = 0;
				nextnode++;
			}

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

		nreg += newreg;
	}

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

	//fprintf(stderr, "%d %d\n", clock(), nextnode);

	return 0;
}