Cod sursa(job #1712744)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 3 iunie 2016 16:30:08
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>

using namespace std;

ifstream fin("regiuni.in");
ofstream fout("regiuni.out");

const int dim = 1005;

int n, m;

set< pair<int, int> > hashes;

struct {
	int a, b, c;
} lines[dim];

int getRelativePos(int x, int y, int a, int b, int c) {

	long long aux = 1LL * a*x + 1LL * b*y + c;
	return (aux == 0 ? 0 : (aux > 0 ? 1 : -1));

}

pair<int, int> getHash(const vector<int> cur) {

	static int mod1 = 666013, mod2 = 666011;
	static int base1 = 73, base2 = 83;

	int h1 = 0, h2 = 0;
	for (auto it : cur) {

		h1 = (h1 * base1 + (it + 1)) % mod1;
		h2 = (h2 * base2 + (it + 1)) % mod2;

	}

	return make_pair(h1, h2);

}

int main() {

	fin >> n >> m;

	for (int i = 1; i <= n; ++i)
		fin >> lines[i].a >> lines[i].b >> lines[i].c;

	for (int i = 1; i <= m; ++i) {

		int x, y;
		fin >> x >> y;

		vector<int> cur;
		for (int j = 1; j <= n; ++j)
			cur.push_back(getRelativePos(x, y, lines[j].a, lines[j].b, lines[j].c));

		pair<int, int> hash = getHash(cur);
		hashes.insert(hash);

	}

	fout << hashes.size();

	return 0;

}

//Trust me, I'm the Doctor!