Cod sursa(job #191305)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 25 mai 2008 22:07:59
Problema Regiuni Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define NMAX 1024
struct pct{int x,y;};
struct dr{int a,b,c;};
const unsigned long cx=666013;

unsigned p2[NMAX];

int fcmp2(void const* a,void const* b){
if(*((unsigned long *)a)>*((unsigned long *)b))return 1;
else if(*((unsigned long *)a)<*((unsigned long *)b))return -1;
	 else return 0;
}

unsigned long fcrc(unsigned c[],int count){
unsigned long cc=0L;
for(int i=0;i<count;i++){
	cc=c[i]*p2[i]+cc;
	if(cc>cx) cc%=cx;
	}
return cc;
}

int main(){
freopen("regiuni.in","r",stdin);
freopen("regiuni.out","w",stdout);
int n,m,i,j,k,nrg=1;
long  poz;
char cif[8]={1,2,4,8,16,32,64,128};
unsigned cod[NMAX];
unsigned long crc[NMAX]={0};
pct p[NMAX];
dr d[NMAX];
scanf("%d%d",&n,&m);
p2[0]=1L;
for(k=1;k<=n;k++){
	p2[k]=p2[k-1]*2;
	if(p2[k]>cx) p2[k]%=cx;
	}
for(i=0;i<n;i++) scanf("%d%d%d",&d[i].a,&d[i].b,&d[i].c);
for(j=0;j<m;j++) scanf("%d%d",&p[j].x,&p[j].y);
for(j=0;j<m;j++){
 //	scanf("%d%d",&x,&y);
	for(i=0;i<n;i++){
		poz=d[i].a*p[j].x+d[i].b*p[j].y+d[i].c;
		if(poz>0L) cod[i]=1;
		else cod[i]=0;
		}
		crc[j]=fcrc(cod,n);
	}
qsort(crc,m,sizeof(crc[0]),fcmp2);

for(j=1;j<m;j++)
	if(crc[j]!=crc[j-1]) nrg++;
printf("%d",nrg);
return 0;
}