Cod sursa(job #37677)

Utilizator blasterzMircea Dima blasterz Data 25 martie 2007 11:51:52
Problema Regiuni Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.63 kb
#include <cstdio>
#include <set>
#include <algorithm>
#include<bitset>
#define maxn 1024
using namespace std;
struct point { int x, y;};

point x[maxn];
int a[maxn], b[maxn], c[maxn];
int n, m;
void citire()
{
	freopen("regiuni.in", "r", stdin);
	scanf("%d %d\n", &n, &m);
	int i;
	for(i=1;i<=n;i++) scanf("%d %d %d\n", &a[i], &b[i], &c[i]);
	for(i=1;i<=m;i++) scanf("%d %d\n", &x[i].x, &x[i].y);
}
int s[maxn];


int verifica(int i, int j)
{
	point t=x[j];
	long long r=t.x*a[i]+t.y*b[i]+c[i];
	if(r>0) return 1;
	return 0;
}

unsigned int A[maxn][maxn/32];
int len[maxn];
void calcul()
{
	int i, j;
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		if(verifica(i, j)) A[i][j>>5]|=1<<(j&31);
		
	}
	int Q[maxn], t=0, k, ok;
	Q[1]=1;
	t=1;
	for(i=2;i<=n;i++)
	{	ok=1;
		for(j=1;j<=t;j++)
		{
			
			for(k=0;k<=n>>5;k++)
				if(A[Q[j]][k]!=A[i][k]) {ok=0;break;}
			if(ok==1) break;
				//	if(ok) printf("%d ", i);
		}
	//printf("(%d) ", ok);
		if(!ok) { Q[++t]=i;};
			
			//if(A[Q[j]].a==A[i].a) {Q[++t]=i;break;}
	}
	//	printf("da\n");
		//printf("%d\n\n", t);
		/*
		for(i=1;i<=n;i++)
		{
			for(k=0;k<=n>>5;k++) 
				for(t=0;t<32;t++) 
					if(A[i][k]& (1<<t) ) printf("1 "); else printf("0 ");//printf("%lld ", A[i][k]);
			printf("\n");
		}
		*/
		//printf("\n\n");
		/*
		for(i=1;i<=n;i++)
		{
			for(k=0;k<=n>>5;k++) printf("%d ", A[i][k]);
			printf("\n");
		}
		*/
			//printf("%d\n", t);
	//printf("%d\n", sizeof(A));
	freopen("regiuni.out", "w", stdout);
printf("%d\n", t);
	
//	for(i=1;i<=n;i++) printf("%d ", s[i]);
}

int main()
{
	citire();
	calcul();
	return 0;
}