Cod sursa(job #88333)

Utilizator blasterzMircea Dima blasterz Data 1 octombrie 2007 18:51:45
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
using namespace std;
#include <cstdio>
#include <string>
#define maxn 500
#define pb push_back
#define sh short

inline int oki(sh int x, sh int y,  sh int a, sh int b, sh int c)
{
	int t=a*x+b*y+c;
	if(t<=0) return 0;
	return 1;
}


int main()
{
	int H[maxn][(maxn/32)+1];
	memset(H, 0, sizeof(H));
sh int a[maxn], b[maxn], c[maxn],x[maxn],y[maxn];
int M, N;
sh ng[maxn];
memset(ng, 0, sizeof(ng));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));

	freopen("regiuni.out","w",stdout);
freopen("regiuni.in","r",stdin);
	scanf("%d %d\n", &M, &N);
int i, j,k, Nr=0,Nr2, n;
	for(i=1;i<=M;++i) scanf("%d %d %d\n", &a[i], &b[i], &c[i]);
	for(i=1;i<=N;++i) scanf("%d %d\n", &x[i], &y[i]);
	
	//solve();
//	solve2();
	for(i=1;i<=N;++i) H[0][i>>5]|=(1<<(i&31));
	ng[0]=N;
	
	for(i=1;i<=M;++i)
	{	Nr2=Nr;
		for(j=0;j<=Nr;++j)
			if(ng[j])
			{
				n=ng[j];
				char p[maxn/32+1];
				memset(p, 0, sizeof(p));
				int np=0;
				for(k=1;k<=N;++k)
					if(H[j][k>>5]&(1<<(k&31)))
						if(oki(x[k], y[k], a[i], b[i], c[i])) 
							p[k>>5]|=(1<<(k&31)), ++np;
					
					if(np==n || np==0);
					else
					{
						
						for(k=1;k<=N;++k) if(p[k>>5]&(1<<(k&31))) H[j][k>>5]&=~(1<<(k&31));
						++Nr2;
						for(k=1;k<=N;++k) if(p[k>>5]&(1<<(k&31))) H[Nr2][k>>5]|=(1<<(k&31));
						ng[Nr2]=np;
						ng[j]=n-np;
					}
			}
			Nr=Nr2;
	}

//printf("%d\n", Nr);
Nr2=0;
for(i=0;i<=Nr;++i) if(ng[i]) ++Nr2; 
printf("%d\n", Nr2);
	
//	printf("%d\n", sizeof(a)+sizeof(b)+sizeof(c)+sizeof(x)+sizeof(y)+sizeof(ng)+sizeof(H));	

	return 0;
}