Cod sursa(job #38304)

Utilizator filipbFilip Cristian Buruiana filipb Data 25 martie 2007 17:13:12
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <string.h>
#define NMax 1005

int N, M, A[NMax], B[NMax], C[NMax], cnt;
int T[NMax * NMax][2], NODES = 0;
char s[NMax];

char semn(int A, int B, int C, int x, int y)
{
     int E = A * x + B * y + C;
     
     if (E < 0) return '0';
     return '1';     
}

int OK;

void insert_trie(int nod, int len)
{
     int c;
     
     if (len == N)
     {
         cnt += OK;    
         return ;
     }
     
     c = s[len]-'0';
     if (T[nod][c] == -1)
     { OK = 1; T[nod][c] = (++NODES); insert_trie(NODES, len+1); }
     else
         insert_trie(T[nod][c], len+1);
     
}

int main(void)
{
    int i, j, x, y;
    
    freopen("regiuni.in", "r", stdin);
    freopen("regiuni.out", "w", stdout);
    
    scanf("%d %d", &N, &M);
    for (i = 0; i < N; i++)
        scanf("%d %d %d", &A[i], &B[i], &C[i]);
        
    memset(T, -1, sizeof(T));
    for (i = 1; i <= M; i++)
    {
        scanf("%d %d", &x, &y);
        for (j = 0; j < N; j++)
            s[j] = semn(A[j], B[j], C[j], x, y);

        OK = 0;      
        insert_trie(0, 0);
    }
    
    printf("%d\n", cnt);
    
    return 0;
}