Cod sursa(job #857573)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 17 ianuarie 2013 23:25:31
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<stdio.h>

#define maxdim 1005

FILE*f=fopen("regiuni.in","r");
FILE*g=fopen("regiuni.out","w");

const int mod1 = 700001,mod2 = 700003;
int m,n;
int a[maxdim],b[maxdim],c[maxdim],hash1[maxdim],hash2[maxdim];

int main () {
	
	fscanf(f,"%d %d",&m,&n);
	for ( int i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d %d",&a[i],&b[i],&c[i]);
	}
	
	int x,y;
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		
		for ( int j = 1 ; j <= m ; ++j ){
			long long d = 1LL*x*a[j] + 1LL*y*b[j] + c[j];
			
			if ( d < 0 ){
				hash1[i] = (hash1[i]+hash1[i]);
				if ( hash1[i] >= mod1 )	hash1[i] -= mod1;
				hash2[i] = (hash2[i]+hash2[i]);
				if ( hash2[i] >= mod2 )	hash2[i] -= mod2;
			}
			else{
				hash1[i] = (hash1[i]+hash1[i]+1);
				if ( hash1[i] >= mod1 )	hash1[i] -= mod1;
				hash2[i] = (hash2[i]+hash2[i]+1);
				if ( hash2[i] >= mod2 )	hash2[i] -= mod2;
			}
		}
	}
	
	int sol = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		
		int grup = 1;
		for ( int j = i+1 ; j <= n ; ++j ){
			if ( hash1[i] == hash1[j] && hash2[i] == hash2[j] ){
				grup = 0;
				break ;
			}
		}
		
		sol += grup;
	}
	
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}