Cod sursa(job #381913)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 11 ianuarie 2010 23:23:11
Problema Regiuni Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <algorithm>
#define MAXN 1024
#define MAXM 1024
#define MOD 1000000007
using namespace std;
struct dreapta{ short a,b,c; } Dr[MAXN];
struct punct{ short x,y; } Pt[MAXM];
int N,M,hash[MAXM];

void build_hash(int point){
	int pw2=1;
	hash[point]=0;

	for (int i=1;i<=N;++i){
		int ecu=(int)Dr[i].a*Pt[point].x+Dr[i].b*Pt[point].y+Dr[i].c;
		if (ecu>0) hash[point]+=pw2;
		if (hash[point]>=MOD) hash[point]-=MOD;
		pw2*=2;
		if (pw2>=MOD) pw2-=MOD;
	}
}



int main(){

	ifstream fi("regiuni.in");
	fi>>N>>M;

	for (int i=1;i<=N;++i) fi>>Dr[i].a>>Dr[i].b>>Dr[i].c;

	for (int i=1;i<=M;++i) fi>>Pt[i].x>>Pt[i].y;

	fi.close();

	for (int i=1;i<=M;++i) build_hash(i);

	sort(hash+1,hash+M+1);

	int SOL=0;

	for (int i=1;i<=M;++i)
		if (i==1 || hash[i]!=hash[i-1]) ++SOL;

	ofstream fo("regiuni.out");
	
	fo<<SOL<<"\n";
	
	fo.close();

	return 0;
}