Cod sursa(job #37799)

Utilizator VmanDuta Vlad Vman Data 25 martie 2007 12:38:59
Problema Regiuni Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.45 kb
#include <stdlib.h>
#include <stdio.h>
#define Nmax 1001

int N,M,i,j,g[Nmax][Nmax],a[Nmax],b[Nmax],c[Nmax],x[Nmax],y[Nmax],ind[Nmax],nr;

void qsort(int l,int r)
{
int i,j,aux,m,k,ok;
i=l;
j=r;
m=(i+j)/2;
while (i<=j)
      {
      ok=1;
      while ((ok==1)&&(i<m))
	    {
	    for (k=0;k<N;++k)
		if (g[ind[i]][k]>g[ind[m]][k])
		   {
		   ok=0;
		   break;
		   }
	    if (ok==1) ++i;
	    }
      ok=1;
      while ((ok==1)&&(j>m))
            {
            for (k=0;k<N;++k)
                if (g[ind[j]][k]<g[ind[m]][k])
                   {
                   ok=0;
                   break;
                   }
            if (ok==1) --j;
            }
      if (i<=j)
         {
         aux=ind[i];
         ind[i]=ind[j];
         ind[j]=aux;
         ++i;
         --j;
         }
      }
if (i<r) qsort(i,r);
if (l<j) qsort(l,j);
}

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