Cod sursa(job #48719)

Utilizator eferLiviu Ciortea efer Data 5 aprilie 2007 00:11:25
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
using namespace std;

#define REP(i, N) for (int i = 0; i < (N); ++i)

const int MAXN = 1024;

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

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

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

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]);
		node *p = new node;
		p->info = i;
		p->next = regs[0];
		regs[0] = p;
	}

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

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

	return 0;
}