Cod sursa(job #41178)

Utilizator moga_florianFlorian MOGA moga_florian Data 28 martie 2007 00:14:34
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
using namespace std;
#include<fstream>
#include<stdio.h>
#define nmax 1002
#define lmax 35
#define cst 30

int a[nmax],b[nmax],c[nmax];
struct nod{int x,y;nod* next;};
typedef nod* list;
list aa[1003],q;

struct sir{int x,y;};
sir g1[1003],g2[1003];

int ng1,ng2;

void bagagr1(int p)
{
int i;
for(i=1;i<=ng1;i++)
   {
   if(aa[p]==NULL)
      {
      aa[p]=new nod;
      aa[p]->next=NULL;           
      }               
   else
      {
      q=new nod;
      q->next=aa[p];
      aa[p]=q;
      } 
   aa[p]->x=g1[i].x;
   aa[p]->y=g1[i].y;
   }
}

void bagagr2(int p)
{
int i;
for(i=1;i<=ng2;i++)
   {
   if(aa[p]==NULL)
      {
      aa[p]=new nod;
      aa[p]->next=NULL;           
      }               
   else
      {
      q=new nod;
      q->next=aa[p];
      aa[p]=q;
      } 
   aa[p]->x=g2[i].x;
   aa[p]->y=g2[i].y;
   }
}

int main()
{
FILE *fin=fopen("regiuni.in","r"),
     *fout=fopen("regiuni.out","w");
int m,n,i,j,k,ngr=1;
fscanf(fin,"%d%d",&n,&m);

for(i=1;i<=n;i++)
  fscanf(fin,"%d%d%d",&a[i],&b[i],&c[i]);

for(i=1;i<=m;i++)
  {
  fscanf(fin,"%d%d",&j,&k);
  if(aa[1]==NULL)
    {
    aa[1]=new nod;
    aa[1]->next=NULL;
    }
  else
    {
    q=new nod;
    q->next=aa[1];
    aa[1]=q;         
    }
  aa[1]->x=j;
  aa[1]->y=k;
  }
  
int noi;
for(i=1;i<=n;i++)
  {
  noi=0;
  for(j=1;j<=ngr;j++)
     {
     ng1=ng2=0;
     while(aa[j])
       {
       if(a[i]*aa[j]->x+b[i]*aa[j]->y+c[i]>0)
            {
            g1[++ng1].x=aa[j]->x;
            g1[ng1].y=aa[j]->y;
            }
       else
            {
            g2[++ng2].x=aa[j]->x;
            g2[ng2].y=aa[j]->y;                   
            }
       q=aa[j];
       aa[j]=aa[j]->next;
       delete q;
       }                    
             
     if(ng1>ng2)
        {
        bagagr1(j);
        if(ng2)
           {
           noi++;
           bagagr2(ngr+noi);
           }
        }
     else
        {
        bagagr2(j);
        if(ng1)
           {
           noi++;
           bagagr1(ngr+noi);    
           }    
        }
     }                 
  ngr+=noi;
  }
fprintf(fout,"%d\n",ngr);

fclose(fin);
fclose(fout);
return 0;
}