Cod sursa(job #43959)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 30 martie 2007 18:44:22
Problema Regiuni Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>
#define NMAX 1010
#define MAX(a,b) ((a)>(b)?(a):(b))

int N, M, D[NMAX][3], P[NMAX][2];
int Reg[NMAX], A[NMAX];

int main()
{
        int i, j, nreg = 0;
        long long max;

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

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

        for (i = 1; i <= M; i++)
                scanf("%d %d", P[i], P[i]+1);

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

        for (i = 1; i <= N; i++)
        {
            memset(A,0,sizeof(A));
            for (j = 1; j <= M; j++)
                if ((P[j][0]*D[i][0]+P[j][1]*D[i][1]+D[i][2]) > 0)
                {
                   if (A[ Reg[j] ] == 0)  A[ Reg[j] ] = 1;
                }
                else
                {
                   if (A[ Reg[j] ] == 1) nreg++;
                   A[ Reg[j] ] = 2; Reg[j] = nreg;
                }
        }

        for (i = 1; i <= M; i++)
            for (j = i+1; j <= M; j++)
                if (Reg[i] == Reg[j]) Reg[j] = 0;
        for (i = 1; i <= M; i++) nreg += (Reg[i]>0);

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

        return 0;
        
}