Cod sursa(job #42762)

Utilizator wefgefAndrei Grigorean wefgef Data 29 martie 2007 15:06:14
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>

#define Nmax 1024

int m, n;
int a[Nmax], b[Nmax], c[Nmax];
int x[Nmax], y[Nmax];
int v[Nmax], u[Nmax], tag[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 = 1, ind;
	char v0, v1;
	
	for (i = 1; i <= n; ++i)
	{
		v[i] = i;
		tag[i] = 1;
	}
		
	for (i = 1; i <= m; ++i)
	{
		nou = 0;
		for (j = 1; j <= n; ++j)
		{
			for (k = j; k <= n && tag[v[j]] == tag[v[k]]; ++k); --k;
			
			v0 = v1 = 0;
			for (l = j; l <= k; ++l)
				if (semn(i, v[l]) == 0) v0 = 1;
				else v1 = 1;
			
			if (v0 && v1)
			{
				ind = j-1;
				for (l = j; l <= k; ++l)
					if (semn(i, v[l]) == 0)
					{
						++ind;
						u[ind] = v[l];
						tag[v[l]] = nou+1;
					}
				for (l = j; l <= k; ++l)
					if (semn(i, v[l]) == 1)
					{
						++ind;
						u[ind] = v[l];
						tag[v[l]] = nou+2;
					}					
				for (l = j; l <= k; ++l)
					v[l] = u[l];
				nou += 2;
			}
			else ++nou;
			
			j = k;
		}
	}
	printf("%d\n", nou);
}

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