Cod sursa(job #48436)

Utilizator eferLiviu Ciortea efer Data 4 aprilie 2007 19:34:20
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <utility>
#include <string>
using namespace std;

#define REP(i, N) for (int i = 0; i < (N); ++i)
#define REPV(i, a, b) for (int i = (a); i <= (b); ++i)
#define REPD(i, N) for (int i = (N)-1; i >= 0; --i)
#define REPVD(i, b, a) for (int i = (b); i >= (a); --i)
#define REPIT(it, v) for (it = (v).begin(); it != (v).end(); ++it)
#define SZ(a) ((int)(a).size())
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define ALL(a) (a).begin(), (a).end()
#define CLR(a) memset((a), 0, sizeof(a))
#define MSET(a, v) memset((a), v, sizeof(a))
#define CPY(dest, source) memcpy(dest, source, sizeof(dest))

typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef set<int> SI;
typedef map<int, int> MII;
typedef deque<int> QI;
typedef deque<PII> QPII;

const int MAXN = 1024;
const int MAXM = 1024;
int M, N, a[MAXM], b[MAXM], c[MAXM], x[MAXN], y[MAXN], R = 1;
VI regs[MAXM];

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

int main() {
	//srand(6585);

//start:
	freopen("regiuni.in", "rt", stdin);
	//freopen("regiuni.out", "wt", stdout);

	scanf("%d %d", &M, &N);
	//N = M = 1000;

	REP(i, M) {
		scanf("%d %d %d", &a[i], &b[i], &c[i]);
		//a[i] = rand() & 1023;
		//b[i] = rand() & 1023;
		//c[i] = (rand() & 32767) - 16384;
	}

	//R = 1;
	//regs[0].clear();

	REP(i, N) {
		scanf("%d %d", &x[i], &y[i]);
		//x[i] = rand() & 1023;
		//y[i] = rand() & 1023;
		regs[0].PB(i);
	}

	REP(i, M) {
		int tmp = R;
		REP(r, tmp) {
			VI reg, nreg;
			VI::iterator it;
			bool h1 = false, h2 = false;
			for (it = regs[r].begin(); it != regs[r].end(); ++it) {
				int s = sign(a[i] * x[*it] + b[i] * y[*it] + c[i]);
				if (s == 1) { reg.PB(*it); h1 = true; }
				else { nreg.PB(*it); h2 = true; }
			}
			if (h1 && h2) {
				regs[r] = reg;
				regs[R++] = nreg;
			}
		}
	}

	printf("%d\n", R);
	
	//goto start;

	return 0;
}