Cod sursa(job #39842)

Utilizator vrajalaMihai Viteazu, razboinicu luminii vrajala Data 27 martie 2007 01:24:40
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdlib.h>
#include <stdio.h>
#define Nmax 1002

long N,M,a[Nmax],b[Nmax],c[Nmax],x[Nmax],y[Nmax],g[Nmax],r[Nmax],ind[Nmax],i,j,k,k2,pi,nr;

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]);
     g[i]=i;
     }
 fclose(stdin);
 k=0;
 ind[M]=M+1;
 for (i=0;i<N;++i)
     {
      j=0;
      nr=0;
      k=0;
      while (j<M)
         {
          k2=0;
          pi=k;
          do
                {
                if (a[i]*x[g[j]]+b[i]*y[g[j]]+c[i]<0)
                   {
                   g[k]=g[j];
                   ind[k++]=nr;
                   }
                   else r[k2++]=g[j];
                ++j;
                }
          while ((ind[j-1]==ind[j])&&(j<M));
          if (k!=pi) ++nr;
          if (k2!=0)
             {
	     while (k2>0)
		 {
		 g[k]=r[--k2];
                 ind[k++]=nr;
                 }
             ++nr;
             }
         }
     }
 /*nr=0;
 for (i=0;i<N;++i)
     if (ind[i]!=ind[i+1]) ++nr;*/
 freopen("regiuni.out","w",stdout);
 printf("%d",nr);
 fclose(stdout);
 return 0;
}