Cod sursa(job #38520)

Utilizator goguGogu Marian gogu Data 25 martie 2007 21:15:36
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#define MOD1 2051222731
#define MOD2 1734135123
#define MaxN 1010

unsigned h1[MaxN], h2[MaxN];
int n, m, rez, ok[MaxN];
int a[MaxN], b[MaxN], c[MaxN];

void bf(int v)
{
    rez++;
    c[0]=v; ok[v]=1;
    int i, j=0, k, nr=1;
    while (j<nr){
          k=c[j++];
          for (i=0; i<n; i++)
              if ((ok[i]==0) && (h1[k]==h1[i]) && (h2[k]==h2[i]))
                 ok[i]=1, c[nr++]=i;
    }
}

int main()
{
    int i,j;
    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 (i=0; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        h1[i]=h2[i]=0;
        for (j=0; j<m; j++){
            int k=a[j]*x + b[j]*y +c[j];
            if (k<0) k=0; else k=1;
            h1[i]=h1[i]*2+k;
            if (h1[i]>=MOD1) h1[i]-=MOD1;
            h2[i]=h2[i]*2+k;
            if (h2[i]>=MOD2) h2[i]-=MOD2;
        }
    }
    for (i=0; i<n; i++)
        if (!ok[i]) bf(i);
    printf("%d\n", rez);
    return 0;
}