Cod sursa(job #48680)

Utilizator eferLiviu Ciortea efer Data 4 aprilie 2007 23:41:37
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
using namespace std;

#define REP(i, N) for (int i = 0; i < (N); ++i)
#define SZ(a) ((int)(a).size())
#define PB push_back

const int MAXN = 1024;
const int MAXM = 1024;

struct node {
	int info;
	node* next;
};

int M, N, a[MAXM], b[MAXM], c[MAXM], x[MAXN], y[MAXN], R = 1;
node* regs[MAXM];

inline int sign(int x) {
	return x > 0 ? 1 : -1;
}

inline void insert_node(node*& reg, int n) {
	node* p = new node;
	p->info = n;
	p->next = reg;
	reg = p;
}

int main() {
	freopen("regiuni.in", "rt", stdin);
	freopen("regiuni.out", "wt", stdout);

	scanf("%d %d", &M, &N);

	REP(i, M) scanf("%d %d %d", &a[i], &b[i], &c[i]);

	REP(i, N) {
		scanf("%d %d", &x[i], &y[i]);
		insert_node(regs[0], i);
	}

	REP(i, M) {
		int save = R;
		REP(r, save) {
			node *reg = NULL, *nreg = NULL;
			for (node* p = regs[r]; p; p = p->next) {
				int s = sign(a[i] * x[p->info] + b[i] * y[p->info] + c[i]);
				if (s == 1) insert_node(reg, p->info);
				else insert_node(nreg, p->info);
			}
			if (reg && nreg) {
				for (node* p = regs[r]; p; ) {
					node *tmp = p;
					p = p->next;
					delete tmp;
				}
				regs[r] = reg;
				regs[R++] = nreg;
			}
		}
	}

	printf("%d\n", R);

	return 0;
}