Cod sursa(job #308970)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 29 aprilie 2009 09:49:09
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>

using namespace std;

#define Nmax 1010
#define file_in "regiuni.in"
#define file_out "regiuni.out"

struct dreapta
{
	int a,b,c;
}
d[Nmax];

struct pct
{
	int x,y;
}
p[Nmax];

int r;
int n,m;
int v[27*Nmax][2];

int main()
{
	int i,j,t,nr,rg,nrg;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n,&m);
	
	for (i=1;i<=n;++i)
		 scanf("%d %d %d", &d[i].a, &d[i].b, &d[i].c);
	nrg=0;
	nr=0;
	v[0][0]=v[0][1]=0;
	for (i=1;i<=m;++i)
	{
		scanf("%d %d", &p[i].x, &p[i].y);
		rg=t=0;
		for (j=1;j<=n;++j)
		{
			r=d[j].a*p[i].x+d[j].b*p[i].y+d[j].c;
			if (r>0)
				r=1;
			else
				r=0;
		    if (!v[t][r])
			{
			  rg=1;
			  nr++;
			  v[t][r]=nr;
			  v[nr][0]=v[nr][1]=0;
			}
			t=v[t][r];
		}
		nrg+=rg;
	}
	
	printf("%d", nrg);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}