Cod sursa(job #37852)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 25 martie 2007 12:51:25
Problema Regiuni Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.19 kb
#include <cstdio>

struct dreapta { int a, b, c; };
struct punct { int x, y; };

const int NMAX = 1024;

int N, M;
dreapta D[NMAX];
punct P[NMAX];
bool beg[NMAX];

void read(void) {
	FILE *fin = fopen("regiuni.in", "rt");
	int i;

	fscanf(fin, " %d %d", &N, &M);

	for (i = 0; i < N; ++i)
		fscanf(fin, " %d %d %d", &D[i].a, &D[i].b, &D[i].c);
	
	for (i = 0; i < M; ++i)
		fscanf(fin, " %d %d", &P[i].x, &P[i].y);

	fclose(fin);
}

inline int semn(punct p, dreapta d) {
	return d.a * p.x + d.b * p.y + d.c > 0 ? 1 : -1;
}

void partitie(int p, int r, dreapta d) {
	int i = p, j = r, v;
	punct aux;

	v = semn(P[p], d);

	while (i < j) {
		do { --j; } while ( j >= i && semn(P[j], d) * v == 1 );

		if (i <= j) {
			aux = P[i]; P[i] = P[j]; P[j] = aux;
			++i;
		}
	}

	beg[i] = true;
}

void sortam(void) {
	int i, j, k;

	beg[0] = true;

	for (k = 0; k < N; ++k)
		for (i = 0; i < M; i = j) {
			
			for (j = i + 1; j < M && beg[j] == false; ++j);
	
			partitie(i, j, D[k]);

		}
}

void write(void) {
	FILE *fout = fopen("regiuni.out", "wt");
	int i, rez = 0;

	for (i = 0; i < M; ++i)
		if (beg[i]) ++rez;

	fprintf(fout, "%d\n", rez);

	fclose(fout);
}

int main() {

	read();

	sortam();

	write();

	return 0;
}