Cod sursa(job #42752)

Utilizator wefgefAndrei Grigorean wefgef Data 29 martie 2007 14:55:05
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>

#define Nmax 1024

int m, n;
int a[Nmax], b[Nmax], c[Nmax];
int x[Nmax], y[Nmax];
int v[Nmax];

void readdata()
{
	freopen("regiuni.in", "r", stdin);
	freopen("regiuni.out", "w", stdout);
	
	int i;
	
	scanf("%d %d", &m, &n);
	
	for (i = 1; i <= m; ++i)
		scanf("%d %d %d", &a[i], &b[i], &c[i]);
	for (i = 1; i <= n; ++i)
		scanf("%d %d", &x[i], &y[i]);
}

int semn(int dr, int pt)
{
	return a[dr]*x[pt] + b[dr]*y[pt] + c[dr] > 0;
}

void solve()
{
	int i, j, k, l;
	int nou;
	char v0, v1;
	
	for (i = 1; i <= n; ++i)
		v[i] = 1;
		
	for (i = 1; i <= m; ++i)
	{
		nou = 0;
		for (j = 1; j <= n; ++j)
		{
			for (k = j; k <= n && v[j] == v[k]; ++k); --k;
			
			v0 = v1 = 0;
			for (l = j; l <= k; ++l)
				if (semn(i, l) == 0) v0 = 1;
				else v1 = 1;
			
			for (l = j; l <= k; ++l)
				if (!(v0 && v1)) v[l] = nou+1;
				else
					if (semn(i, l) == 0) v[l] = nou+1;
					else v[l] = nou+2;
					
			nou += v0+v1;
			
			j = k;
		}
	}
	printf("%d\n", nou);
}

int main()
{
	readdata();
	solve();
	return 0;
}