Cod sursa(job #42548)

Utilizator pocaituDavid si Goliat pocaitu Data 29 martie 2007 12:02:08
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#include<fstream.h>
#define dmax 33
#define nmax 1005
#define l 32
#define grmax 100

int i,n,d,j,ad1,ad2,k,nr,a[nmax],b[nmax],c[nmax],x[nmax],y[nmax],nr1,m;
unsigned long gr[grmax][dmax],g1[dmax],g2[dmax];


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]);
 for(i=0;i<m;i++)
  scanf("%d%d",&x[i],&y[i]);
for(d=0;d*l<m;d++)
 for(i=0;i<=l-1&&i+d*l<m;i++)
   gr[1][d]|=1<<i;
nr=1;
for(i=1;i<=n;i++)
 {
  for(d=1,nr1=nr;d<=nr;d++)
   {memset(g1,0,sizeof(g1));
	memset(g2,0,sizeof(g2));

	for(j=0;j*l<m;j++)
		for(k=0;k<=l-1&&k+j*l<m;k++)
		 if(gr[d][j]&1<<k)
		   {if(a[i]*x[j*l+k]+b[i]*y[j*l+k]+c[i]>0)
			  g1[j]|=1<<k;
			else
			  g2[j]|=1<<k;
			}

	for(j=0,ad1=ad2=0;j*l<m;j++)
		{if(g1[j])
		  ad1=1;
		 if(g2[j])
		   ad2=1;
		 }
	if(ad1&&ad2)
	 {memcpy(gr[d],g1,sizeof(g1));
	  memcpy(gr[++nr1],g2,sizeof(g2));
	  }
	}
  nr=nr1;
  }
freopen("regiuni.out","w",stdout);
printf("%d",nr);
fclose(stdout);
return 0;
}