Cod sursa(job #301403)

Utilizator katakunaCazacu Alexandru katakuna Data 8 aprilie 2009 10:27:57
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
using namespace std;
#include <cstdio>
#include <vector>

#define Nmax 1010
vector <int> gr[Nmax];

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];


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;
	gr[1].push_back(m);
	for(i = 1; i <= m; i++){
		fscanf(f,"%d %d", &p[i].x, &p[i].y);
		gr[1].push_back(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].clear();
				gr[j].push_back(sus[0]);
				for(l = 1; l <= sus[0]; l++)
					gr[j].push_back(sus[l]);
				
				gr[++nr].push_back(jos[0]);
				for(l = 1; l <= jos[0]; l++)
					gr[nr].push_back(jos[l]);
				
			}
		}
	}

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

	return 0;

}