Cod sursa(job #40109)

Utilizator goguGogu Marian gogu Data 27 martie 2007 11:25:45
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#define MOD 2051222731
#define MaxN 1010

unsigned h[MaxN];
int n, m, rez;
short a[MaxN], b[MaxN], c[MaxN];
char ok[MaxN];

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