Cod sursa(job #43948)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 30 martie 2007 18:23:26
Problema Regiuni Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>
#define NMAX 1001
#define BMAX 17
#define mod(a) (((a) >= 63) ? (a)-63:(a))

int N, M, Rep[NMAX], D[NMAX][3];
long long A[NMAX][BMAX+2];

int main()
{
        int i, j, x, y, l, c, max = 0;

        freopen("regiuni.in", "r", stdin);
        scanf("%d %d", &N, &M);

        for (i = 1; i <= N; i++) scanf("%d %d %d", D[i]+0, D[i]+1, D[i]+2);

        for (i = 1; i <= M; i++)
        {
                scanf("%d %d", &x, &y);
                for (j = 1; j <= N; j++)
                    if (D[j][0]*x+D[j][1]*y+D[j][2] > 0)
                    {
                       l = j/62; c = mod(j);
                       for (; c > 62; c = mod(c));
                       A[i][l] += (long long)(1<<c);
                    }
        }

        for (i = 1; i <= M; i++) Rep[i] = i;

        for (i = 1; i < M; i++)
            for (j = i+1; j <= M; j++)
            {
                for (c = 0, l = 1,l = A[i][c]==A[j][c]; l == 1 && c <= BMAX; c++, l = A[i][c]==A[j][c]);
                Rep[j] = ((l==1) ? Rep[i]:Rep[j]);
            }

        for (i = 1; i <= M; i++)
        {
            for (j = i+1; j <= M; j++)
                if (Rep[i] == Rep[j]) Rep[j] = 0;
        }
        for (i = 1; i <= M; i++) max += (Rep[i]>0);

        freopen("regiuni.out", "w", stdout);
        printf("%d\n", max);

        return 0;
        
}