Cod sursa(job #286080)

Utilizator raduzerRadu Zernoveanu raduzer Data 23 martie 2009 13:36:43
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>

const int MAX_N = 1000;

int n, m, z1, z2, sol;
int reg1[MAX_N], reg2[MAX_N], r[MAX_N];

struct punct {
	int x, y;
} p[MAX_N];

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

struct regiune {
	int s, f;
} reg[MAX_N];

int main()
{
	int i, j, k;
	freopen("regiuni.in", "r", stdin);
	freopen("regiuni.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);
	for (i = 1; i <= m; r[i] = i, ++i) scanf("%d %d", &p[i].x, &p[i].y);
	
	reg[1].s = 1, reg[1].f = m, sol = 1;
	
	for (i = 1; i <= n; ++i)
	{
		for (j = 1; j <= m;)
		{
			z1 = z2 = 0;
			
			for (k = reg[j].s; k <= reg[j].f; ++k)
				if (d[i].a * p[r[k]].x + d[i].b * p[r[k]].y + d[i].c > 0) reg1[++z1] = r[k];
				else reg2[++z2] = r[k];
				
			int q = reg[j].f + 1;
			
			if (z1 && z2)
			{
				reg[j].f = j + z1 - 1;
				
				for (k = 1; k <= z1; ++k) r[++j] = reg1[k];
				
				reg[j].s = j;
				reg[j].f = j + z1 - 1;
				for (k = 1; k <= z2; ++k) r[++j] = reg2[k];
				
				++sol;
			}
			
			j = q;
		}
	}
	
	printf("%d\n", sol);
}