Cod sursa(job #38309)

Utilizator ionescu_bogdanIonescu Bogdan-Gabriel ionescu_bogdan Data 25 martie 2007 17:15:51
Problema Regiuni Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define nmax 1024
#define mmax 1024

int n,m,a[mmax],b[mmax],c[mmax],i,j,x,y,ord[nmax],sol;
char s[nmax][mmax/8];

int fc(const void *x,const void *y)
{
    i=0;
    while ((s[*(int*)x][i]==s[*(int*)y][i])&&(i<(m/8+1)))
        ++i;
    return (s[*(int*)x][i]-s[*(int*)y][i]);
}

int main()
{
    freopen("regiuni.in","r",stdin);
    freopen("regiuni.out","w",stdout);

    scanf("%d%d",&m,&n);
    for (i=0;i<m;i++)
        scanf("%d%d%d",a+i,b+i,c+i);
    for (j=0;j<n;j++)
    {
        ord[j]=j;
        scanf("%d%d",&x,&y);
        for (i=0;i<m;i++)
			if ((a[i]*x+b[i]*y+c[i])>0)
                s[j][i/8]|=(1<<(i%8));
    }
    qsort((void*)ord,n,sizeof(ord[0]),fc);
    sol=1;
	for (j=1;j<n;j++)
		if (fc(&ord[j-1],&ord[j]))
			++sol;
    printf("%d\n",sol);

    return 0;
}