Cod sursa(job #381914)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 11 ianuarie 2010 23:26:42
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#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(){

	freopen("regiuni.in","rt",stdin);

	scanf("%d%d\n",&N,&M);

	for (int i=1;i<=N;++i) scanf("%d%d%d\n",&Dr[i].a,&Dr[i].b,&Dr[i].c);

	for (int i=1;i<=M;++i) scanf("%d%d\n",&Pt[i].x,&Pt[i].y);

	fclose(stdin);

	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;

	freopen("regiuni.out","wt",stdout);
	
	printf("%d\n",SOL);
	
	fclose(stdout);

	return 0;
}