Cod sursa(job #191302)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 25 mai 2008 21:36:45
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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 short cx=197;

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

unsigned short fcrc(unsigned short *buf,int count){
register unsigned short cc=0;
unsigned short nc,ub;
int nr;
cc=cx^*buf;
while(count--){
		buf++;
		nc=*buf;
		nr=15;
		while(nr){
			cc=cc<<1;
			ub=nc&1;
			cc|=ub;
			cc=cc^cx;
			nc=nc>>1;
			nr--;
			}
	}
return cc;
}

int main(){
freopen("regiuni.in","r",stdin);
freopen("regiuni.out","w",stdout);
int n,m,i,j,k,nrg=1,l;
long  poz;
char cif[8]={1,2,4,8,16,32,64,128};
unsigned char cod[130];
unsigned short crc[NMAX]={0},cc,cx=197,*pcc;
//char cod[NMAX][NMAX/8+2]={{0}};//,aux[NMAX/8+2];
pct p[NMAX];//={{0,0}},t;
dr d[NMAX];//={{0,0,0}};
scanf("%d%d",&n,&m);
l=n/8;
if(n%8) l++;
if(l%2) l++;
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(k=0;k<l;k++) cod[k]=0;
	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/8]|=cif[i%8];
		}
		crc[j]=fcrc((unsigned short*)cod,l-1);
	}
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;
}


/*
unsigned short cksum(unsigned short *buf,int count){
register unsigned long sum=0;
while(count--){
	sum+=*buf++<16;

	}
}

*/