Cod sursa(job #285559)

Utilizator savimSerban Andrei Stan savim Data 22 martie 2009 18:26:57
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>

#define MAX_N 1024

struct punct {
	int x;
	int y;
} v[MAX_N];

struct drepte {
	int a;
	int b;
	int c;
} dr[MAX_N];

int i, j, k, n, m, sol, x, nr, nxt;
int point[MAX_N], aux[2][MAX_N], start[MAX_N], stop[MAX_N];

void cit() {
	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; i++)
		scanf("%d %d", &v[i].x, &v[i].y);
}

void solve() {
	start[1] = 1; stop[1] = m; sol = 1;
	for (i = 1; i <= m; i++) point[i] = i;
	
	for (i = 1; i <= n; i++) {
		nr = sol;
		
		//vad cum va desparti dreapta i regiunile deja formate
		for (j = 1; j <= m;) {
			aux[0][0] = aux[1][0] = 0;
			for (k = start[j]; k <= stop[j]; k++)
				if (dr[i].a * v[point[k]].x + dr[i].b * v[point[k]].y + dr[i].c < 0) 
					aux[0][++aux[0][0]] = point[k];
				else 
					aux[1][++aux[1][0]] = point[k];
			
			//formez doua noua grupe 
			x = j; nxt = stop[j] + 1;
			if (aux[0][0] && aux[1][0]) {
				stop[x] = x + aux[0][0] - 1;
				for (k = 1; k <= aux[0][0]; k++)
					point[x++] = aux[0][k];
				
				start[x] = x;
				stop[x] = x + aux[1][0] - 1;
				for (k = 1; k <= aux[1][0]; k++)
					point[x++] = aux[1][k];
				
				nr++;
			}
			
			j = nxt;
		}
		
		sol = nr;
	}
	
	printf("%d\n", sol);
}

int main() {

	cit();
	solve();
	
	return 0;
}