Cod sursa(job #37457)

Utilizator georgianaGane Andreea georgiana Data 25 martie 2007 10:00:17
Problema Regiuni Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.48 kb
#include <stdio.h>
#include <string.h>

#define Nmax 1000

int n,m,i,
    a[Nmax],b[Nmax],c[Nmax],x[Nmax],y[Nmax],v[Nmax][Nmax],nr[Nmax];

int side(int p, int d)
{
   int aux=a[d]*x[p]+b[d]*y[p]+c[d];
   if (aux>0) return 1;
   else return -1;
}

int main()
{
   freopen("regiuni.in","r",stdin);
   scanf("%d %d",&n,&m);
   for (i=0;i<n;i++) scanf("%d %d %d",&a[i],&b[i],&c[i]);
   for (i=0;i<m;i++) scanf("%d %d",&x[i],&y[i]);

   memset(nr,0,sizeof(nr));
   int dim=1;
   nr[0]=m;
   for (i=0;i<nr[0];i++) v[0][i]=i;

   for (int d=0;d<n;d++)
      {
         int dim2=dim;
         for (int k=0;k<dim;k++)
            {
               int t=0;
               for (i=0;i<nr[k];i++)
                  if (side(v[k][i],d)==-1)
                    {
                       v[dim2][t++]=v[k][i];
                       v[k][i]=-1;
                    }
               if (t>0)
                 if (t<nr[k])
                   {
                      nr[dim2]=t;
                      dim2++;
                      t=0;
                      for (i=0;i<nr[k];i++)
                         if (v[k][i]>=0) v[k][t++]=v[k][i];
                      nr[k]=t;
                   }
                 else {
                         nr[k]=t;
                         for (i=0;i<t;i++) v[k][i]=v[dim2][i];
                      }
            }
         dim=dim2;
      }

   freopen("regiuni.out","w",stdout);
   printf("%d\n",dim);
   fclose(stdout);
   return 0;
}