Cod sursa(job #286188)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 23 martie 2009 16:14:53
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>

#define maxN	1024
using namespace std;

short int A[maxN], B[maxN], C[maxN], X[maxN], Y[maxN], shuffle[maxN], N, M, NrGrupe = 1;
vector <short int> Grupe[maxN];

int ask (int dr, int i) {
	return (A[dr] * X[i] + B[dr] * Y[i] + C[dr]);
}

void baga_marfa (int dr) {
	int i, j, Nr = NrGrupe;
	vector <short int> now1, now2;
	
	for (i = 1; i <= Nr; ++ i) {
		now1.clear();
		now2.clear();
		for (j = 0; j < Grupe[i].size(); ++ j)
			if (ask(dr, Grupe[i][j]) < 0)
				now1.push_back(Grupe[i][j]);
			else
				now2.push_back(Grupe[i][j]);
		if (now1.size ()) {
			Grupe[i].resize(now1.size());
			Grupe[i] = now1;
			if (now2.size()) {
				Grupe[ ++ NrGrupe].resize(now2.size());
				Grupe[ NrGrupe] = now2;
			}
		} else {
			Grupe[i].resize(now2.size());
			Grupe[i] = now2;
		}
	}
}

void random_shuffle () {
	int i, x, y;
	short int aux;
	srand(time(NULL));
	for (i = 1; i <= N; ++ i)	shuffle[i] = i;
	
	for (i = 1; i <= 3000; ++ i) {
		x = rand () % N + 1;
		y = rand () % N + 1;
		aux = shuffle[x];
		shuffle[x] = shuffle[y];
		shuffle[y] = aux;
	}
}
int main () {
	int i;
	
	freopen("regiuni.in", "r", stdin);
	freopen("regiuni.out", "w", stdout);
	
	scanf("%d%d", &N, &M);
	
	for (i = 1; i <= N; ++ i)
		scanf("%d%d%d", &A[i], &B[i], &C[i]);
	
	for (i = 1; i <= M; ++ i) {
		scanf("%d%d", &X[i], &Y[i]);
		Grupe[1].push_back(i);
	}
	
	random_shuffle();	
	for (i = 1; i <= N; ++ i)
		baga_marfa(shuffle[i]);

	printf("%d\n", NrGrupe);		
}