Cod sursa(job #286086)

Utilizator raduzerRadu Zernoveanu raduzer Data 23 martie 2009 13:55:33
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>

const int MAX_N = 1010;

int n, m, sol, z1, z2;
int r[MAX_N], regiune[2][MAX_N];

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

struct dreapta {
	int a, b, c;
} dr[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", &dr[i].a, &dr[i].b, &dr[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 (dr[i].a * p[r[k]].x + dr[i].b * p[r[k]].y + dr[i].c < 0) regiune[0][++z1] = r[k];
				else regiune[1][++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++] = regiune[0][k];
				
				reg[j].s = j;
				reg[j].f = j + z2 - 1;
				
				for (k = 1; k <= z2; ++k) r[j++] = regiune[1][k];
				
				++sol;
			}
			
			j = q;
		}
	}
	
	printf("%d\n", sol);
}