Cod sursa(job #301310)

Utilizator katakunaCazacu Alexandru katakuna Data 8 aprilie 2009 09:29:04
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>

#define Nmax 1010

struct puncte {int x, y;} p[Nmax];
struct drepte {int a, b, c;} d[Nmax];
int n, m, i, l, j, pt, nr, jos[Nmax], sus[Nmax], gr[Nmax][Nmax];


int main(){

	FILE *f = fopen("regiuni.in", "r");
	FILE *g = fopen("regiuni.out", "w");

	fscanf(f,"%d %d", &n, &m);
	for(i = 1; i <= n; i++)
		fscanf(f,"%d %d %d", &d[i].a, &d[i].b, &d[i].c);
	
	nr = 1;
	for(i = 1; i <= m; i++){
		fscanf(f,"%d %d", &p[i].x, &p[i].y);
		gr[1][++gr[1][0]] = i;
	}
	
	for(i = 1; i <= n; i++){
		for(j = 1; j <= nr; j++){
			sus[0] = 0; jos[0] = 0;
			for(l = 1; l <= gr[j][0]; l++){
				pt = gr[j][l];
				if( d[i].a * p[pt].x + d[i].b * p[pt].y + d[i].c > 0 )
					sus[++sus[0]] = pt;
				
				else 
					jos[++jos[0]] = pt;
				
			}
			
			if( sus[0] && jos[0] ){
				gr[j][0] = sus[0];
				for(l = 1; l <= sus[0]; l++)
					gr[j][l] = sus[l];
				
				gr[++nr][0] = jos[0];
				for(l = 1; l <= jos[0]; l++)
					gr[nr][l] = jos[l];
			}
		}
	}

	fprintf(g,"%d",nr);
	
	fclose(f);
	fclose(g);

	return 0;

}