Cod sursa(job #40110)

Utilizator DorinOltean Dorin Dorin Data 27 martie 2007 11:25:47
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
# include <stdio.h>

using namespace std;

# define input "regiuni.in"
# define output "regiuni.out"

# define maxm 1010
# define max 1001

# define mod 1009

int n,m,x,y,i,k,rez,val,gasit;
int conf[max][32];

long nr,poz;

struct dreapta
{
	int a,b,c;
}v[max];

struct lista
{
	int nr;
	lista * urm;
}*a[maxm];

int main()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout);

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

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

	for(k = 1;k<=m;k++)
	{
		scanf("%d%d",&x,&y);
		nr=1;
		poz = 0;
		for(i=1;i<=n;i++)
		{
			val = v[i].a*x+v[i].b*y+v[i].c;
			
			if(nr >= mod)
				nr %= mod;
			if(val > 0)
			{
				poz+=nr;
			 conf[k][i/32] |= ( 1 << (i%32) );	
            }
			if(poz >= mod)
				poz%=mod;
			nr<<=1;
		}
		if(!a[poz])
		{
			lista * l = new lista ;
			l->nr = k;
			l->urm = a[poz];
			a[poz] = l;

			rez++;
		}
		else
		{		                
			lista * l = a[poz];
			while(l)
			{
				gasit = 1;
				for(i=0;i<=n/32;i++)
				{
					if(conf[k][i] != conf[l->nr][i])
					{
						gasit = 0;
						break;
					}
                }
				if(gasit)
					break;
				l=l->urm;
			}
			if(!gasit)
			{
				rez++;
				lista *f=new lista;
				f->nr=k;
				f->urm = a[poz];
				a[poz] = f;
			}
		}
	}

	printf("%d",rez);

	return 0;
}