Cod sursa(job #40778)

Utilizator raula_sanChis Raoul raula_san Data 27 martie 2007 18:45:41
Problema Regiuni Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <stdio.h>

#define dim 501

int Nd, Np, Sol;
int A[dim], B[dim], C[dim], X[dim], Y[dim], Conf[dim][32], G[dim];

void Read();
void Solve();
void Write();

int Same(int, int);

int main()
{
    Read();
    Solve();
    Write();
    
    return 0;
}

void Read()
{
     freopen("regiuni.in", "r", stdin);
     
     scanf("%d %d", &Nd, &Np);

     int i;
     
     for(i=1; i<=Nd; ++i)
              scanf("%d %d %d", A+i, B+i, C+i);     
              
     for(i=1; i<=Np; ++i)
              scanf("%d %d", X+i, Y+i);
              
     fclose(stdin);
}

void Solve()
{
     int i, j, pos, mask, found, config;
     
     for(i=1; i<=Np; ++i)
              for(j=1; j<=Nd; ++j)
              {
                       config = A[j]*X[i] + B[j]*Y[i] + C[j];
                       
                       if(config < 0)
                       {
				                 pos = j / 32;
                                 mask = 1 << (j % 32);
                                 Conf[i][pos] |= mask;
                       }
              }
     
     G[1] = 1;
     Sol = 1;
     
     for(i=2; i<=Np; ++i)
     {
              found = 0;
              for(j=1; j<i; ++j)
                       if(G[j] && Same(i, j))
                       {
                               found = 1;
                               G[i] = G[j];
                               break;
                       }
              if(!found)
                        G[i] = ++ Sol;
     }
}

void Write()
{
     freopen("regiuni.out", "w", stdout);
     
     printf("%d", Sol);
     
     fclose(stdout);
}

int Same(int i, int j)
{
    int k, limit = Nd / 32;
    
    for(k=0; k<=limit; ++k)
             if(Conf[i][k] != Conf[j][k])
                        return 0;
    return 1;
}