Cod sursa(job #39413)

Utilizator raula_sanChis Raoul raula_san Data 26 martie 2007 18:27:53
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <stdio.h>

#define dim 1 << 10

struct dreapta
{ int a, b, c; } A[dim];

struct punct
{ int x, y; } B[dim];

int n, m, Sol;
int g[dim], conf[dim][dim/32];

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

int same( int x[], int y[] );

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

void Read()
{
     freopen("regiuni.in", "r", stdin);
     
     scanf("%d %d", &n, &m);
     
     int i, j;
     
     for(i=1; i<=n; ++i)
              scanf("%d %d %d", &A[i].a, &A[i].b, &A[i].c);
              
     for(i=1; i<=m; ++i)
              scanf("%d %d", &B[i].x, &B[i].y);
              
     fclose(stdin);
}

void Solve()
{
     int i, j, found;
     long config;
     
     for(i=1; i<=m; ++i)
                  for(j=1; j<=n; ++j)
                  {
                       config = A[j].a * B[i].x + A[j].b * B[i].y + A[j].c;
            
                       if( config > 0 )
                           conf[i][j/32] |= ( 1 << (j%32) );        
                  }     

     Sol = 1;
     g[1] = 1;
     
     for(i=2; i<=m; ++i)
              if( !g[i] )
              {
                  found = 0;
                  
                  for(j=1; j<i; ++j)
                             if( same(conf[i], conf[j]) )
                                 if(g[j])
                                 {
                                         g[i] = g[j];
                                         found = 1;
                                         break;
                                 }
                  if( !found )
                      g[i] = ++ Sol;
              }
}

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

int same( int x[], int y[] )
{
    int i;
    
    for(i=0; i<=n>>5; ++i)
             if( x[i] != y[i] ) return 0;
             
    return 1;
}