Cod sursa(job #40803)

Utilizator raula_sanChis Raoul raula_san Data 27 martie 2007 19:10:51
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>

#define dim 1001

int Nd, Np, Sol;
int A[dim], B[dim], C[dim], X[dim], Y[dim], G[dim], P[dim], N[dim], Ng[dim];

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

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, config;
     
     for(i=1; i<=Np; ++i)
              G[i] = 1;
              
     Sol = 1;
     
     for(i=1; i<=Nd; ++i)
     {
              for(j=1; j<=Sol; ++j)
					   P[j] = N[j] = Ng[j] = 0;
              
              for(j=1; j<=Np; ++j)
              {
                       config = A[i]*X[j] + B[i]*Y[j] + C[i];
                       
                       if(config > 0)
                                 P[G[j]] = 1;
                       if(config < 0)
								 N[G[j]] = 1;
			  }
              
              for(j=1; j<=Np; ++j)
                       if(P[G[j]] && N[G[j]])
                       {
                                  config = A[i]*X[j] + B[i]*Y[j] + C[i];
                                  
                                  if(config < 0)
                                  {
                                            if(!Ng[G[j]])
                                            {
                                                         Ng[G[j]] = ++ Sol;
                                                         G[j] = Ng[G[j]];
                                            }
                                            else
                                                G[j] = Ng[G[j]];
                                  }
                       }
     }
}

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