Cod sursa(job #49968)

Utilizator megabyteBarsan Paul megabyte Data 6 aprilie 2007 17:51:40
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#define INF "regiuni.in"
#define OUF "regiuni.out"
#define NMAX 512
using namespace std;
int a[1000][32]={0};
struct muchie
{
	int a,b,c;
};

struct point
{
	int x,y;
};

int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	register int n,m,i,j,ok,k,nr;
	register int mask[32],gr[NMAX]={0};
//	int a[1000][32]={0};
	muchie ed[NMAX];
	point pt[NMAX];

	fscanf(in,"%d %d",&n,&m);
	for(i=1;i<=n;i++) fscanf(in,"%d %d %d",&ed[i].a,&ed[i].b,&ed[i].c);
	for(i=1;i<=m;i++) fscanf(in,"%d %d",&pt[i].x,&pt[i].y);
	mask[0]=1;
	for(i=1;i<32;i++) mask[i]=(mask[i-1]<<1);

	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			if(ed[i].a*pt[j].x+ed[i].b*pt[j].y+ed[i].c>0) a[i][j/32]|=mask[j%32];
	}
        nr=0;
        for(i=1;i<=m;i++)
	{
		if(!gr[i])
		{
			nr++;
			gr[i]=nr;
			for(j=i+1;j<=m;j++)
			{
				ok=1;
				for(k=0;k<32&&ok;k++)
					if(a[i][k]&a[j][k]) ok=0;
				if(ok) gr[j]=nr;
			}
		}
	}

	fprintf(out,"%d",nr);
	fclose(in);fclose(out);
	return 0;
}