Cod sursa(job #43997)

Utilizator butyGeorge Butnaru buty Data 30 martie 2007 19:30:22
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<stdio.h>
#define sc scanf
#define pr printf
const int Nmax=1024;
const int Mmax=1024;
struct punct
{
	int x,y;
};
struct dreapta
{
	int a,b,c;
};

int N,M,v[Mmax];
int NrG;
punct P[Mmax];
dreapta D[Nmax];
int Gr[256][256];

void cit()
{
	int i;
	freopen("regiuni.in","r",stdin);
	sc("%d%d",&N,&M);
	for(i=1;i<=N;i++)
		sc("%d%d%d",&D[i].a,&D[i].b,&D[i].c);
	for(i=1;i<=M;i++)
		sc("%d%d",&P[i].x,&P[i].y);
}
int semn(dreapta d,punct p)
{
	if(d.a*p.x+d.b*p.y+d.c<0)
		return -1;
	return 1;
}
void rez()
{
	int i,j,x,k,y,NrGNou,GrNou;
	
	for(i=1;i<=M;i++)
		if( semn(D[1],P[i])<0 )
			v[i]=-1;
		else
			v[i]=1;
			
			
	NrG=1;
	for(i=1;i<=M;i++)
		Gr[1][i]=i;	
	Gr[1][0]=M;
	x=v[1];
	GrNou=0;
	y=1;
	for(i=2;i<=M;i++)
		if(v[i]!=x)
		{
			GrNou=1;
			Gr[NrG+1][0]++;
			Gr[NrG+1][Gr[NrG+1][0]]=i;
		}
		else
		{
			y++;
			Gr[NrG][y]=i;
		}
	Gr[NrG][0]=y;
	if(GrNou)
		NrG++;
	
	
	
	for(i=2;i<=N;i++)
	{
		for(j=1;j<=M;j++)
			if( semn(D[i],P[j])<0 )
				v[j]=-1;
			else
				v[j]=1;
		NrGNou=NrG;
		for(j=1;j<=NrG;j++)
		{
			GrNou=0;
			x=v[Gr[j][1]];
			y=1;
			for(k=2;k<=Gr[j][0];k++)
				if(v[Gr[j][k]]!=x)
				{
					GrNou=1;
					Gr[NrGNou+1][0]++;
					Gr[NrGNou+1][Gr[NrGNou+1][0]]=Gr[j][k];
				}
				else
				{
					y++;
					Gr[j][y]=Gr[j][k];
				}
            Gr[j][0]=y;
			if(GrNou)
				NrGNou++;
		}
		NrG=NrGNou;
	}
}
void scr()
{
	freopen("regiuni.out","w",stdout);
	printf("%d\n",NrG);
	fclose(stdout);
}
int main()
{
	cit();
	rez();
	scr();
	return 0;
}