Cod sursa(job #40467)

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

#define dim 1001

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

struct grup
{ int nd; grup *next; } *G[dim];

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

void Add(grup *&, 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 Add(grup *&G, int nd)
{
     grup *x = new grup;
     x->nd = nd;
     x->next = G;
     G = x;
}

void Solve()
{
     int i, j, c1, c2, limit, up; long conf;
     grup *prec;
     
     for(i=1; i<=Np; ++i)
              Add(G[1], i);
     
     Sol = 1;
     
     for(i=1; i<=Nd; ++i)
     {
              limit = Sol;
              for(j=1; j<=limit; ++j)
              {
                       grup *x;
		               c1 = c2 = 0;
		               up = 0;

		               x = G[j];
                       while(x)
                       {
                               conf = A[i]*X[x->nd] + B[i]*Y[x->nd] + C[i];
                               
                               if(conf > 0) c1 = 1;
                               if(conf < 0) c2 = 1;
                               
                               if(c1+c2 == 2) break;
                               
                               x = x->next;
                       } 
                       
                       if(c1+c2 == 2)
                       {
                                x = G[j];
                                prec = NULL;

                                while(x)
                                {
                                        conf = A[i]*X[x->nd] + B[i]*Y[x->nd] + C[i];
                               
                                        if(conf < 0)
                                        {
                                                up = 1;
                                                Add(G[Sol+1], x->nd);
                                       
                                                if(x == G[j])
                                                {
                                                     grup *p = x;
                                                     x = x->next;
                                                     delete p;
                                                }
                                                else
                                                {
                                                    if(x->next == NULL)
                                                    {
                                                               if(prec != NULL)
                                                                       prec->next = NULL;
					                                           delete x;
							                                   x = NULL;
                                                    }
                                                    else
                                                    {
                                                        prec->next = x->next;
                                                        grup *p = x;
                                                        x = x->next;
                                                        delete p;
                                                    }
                                                }
                                       }
                                       else
                                       {
                                           prec= x;
                                           x = x->next;
                                       }
                               }
                       }
                       Sol += up;
              }
     }
}

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