Cod sursa(job #787179)

Utilizator cosminx2003Cosmin Clapon cosminx2003 Data 12 septembrie 2012 19:51:04
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <vector>
#define N 1000
#define M 1000/32+1
#define set(x,k) (x|(1<<k))
#define read(x,k) ((x>>k)&1)

using namespace std;

ifstream f("regiuni.in");
ofstream g("regiuni.out");

short a[N],b[N],c[N];
vector<short> hash[N];
short table[N][M];

int main() {
	int n,m,i,j,t,x,y,key,eq,groups = 0;

	f>>n>>m;
	for(i = 0; i < n; i++)
		f>>a[i]>>b[i]>>c[i];
	for(i = 0; i < m; i++) {
		f>>x>>y;
		key = 0;
		for(j = 0; j < n; j++) {
			table[i][j>>5] = (a[j]*x+b[j]*y+c[j] > 0) ? set(table[i][j>>5],j&31) : table[i][j>>5];
			key += (read(table[i][j>>5],j&31) * (j+1))%N;
		}
		eq = 0;
		for(j = 0; j < hash[key].size(); j++) {
			eq = 1;
			for(t = 0; t <= n>>5; t++) {
				if(table[hash[key][j]][t] != table[i][t]) {
					eq = 0;
					break;
				}
			}
			if(!eq)
				break;
		}
		if(!eq) {
			groups++;
			hash[key].push_back(i);
		}
	}

	g<<groups;

	return 0;
}