Cod sursa(job #38267)

Utilizator DorinOltean Dorin Dorin Data 25 martie 2007 16:53:58
Problema Regiuni Scor 0
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 25032
# define max 1001

# define mod 25031

long n,m,x,y,i,k,rez,val,gasit,t[max],f[max][max];

long nr,poz;

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

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

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

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

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

	for(k = 1;k<=m;k++)
	{
		scanf("%ld%ld",&x,&y);
		nr=1;
		poz = 0;
		for(i=1;i<=n;i++)
		{
			val = v[i].a*x+v[i].b*y+v[i].c;
			nr<<=1;
			if(nr >= mod)
				nr %= mod;
			if(val > 0)
			{
				poz+=nr;
				f[k][i] = 1;
			}
			if(poz >= mod)
				poz%=mod;
		}
		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=1;i<=n;i++)
					if(f[k][i] != f[a[poz]->nr][i])
					{
						gasit = 0;
						break;
					}
				if(gasit)
				{
					x=a[poz]->nr;
					while(t[x])x=t[x];
					t[k]=x;
					break;
				}
				l=l->urm;
			}
			if(!gasit)
			{
				rez++;
				lista *f=new lista;
				f->nr=k;
				f->urm = a[poz];
				a[poz] = f;
			}
		}
	}

	printf("%ld",rez);

	return 0;
}