Cod sursa(job #468176)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 2 iulie 2010 15:26:18
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define Nmax 1002

int N,M,a[Nmax],b[Nmax],c[Nmax],x[Nmax],y[Nmax],g[Nmax],r[Nmax],ind[Nmax],ind2[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;
      memcpy(ind,ind2,sizeof(ind2));
      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];
		   ind2[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];
		 ind2[k++]=nr;
		 }
	     ++nr;
	     }
	 }
     }
 
 freopen("regiuni.out","w",stdout);
 printf("%d",nr);
 fclose(stdout);
 return 0;
}