Cod sursa(job #304310)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 11 aprilie 2009 23:12:56
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <string.h>
#include <stdio.h>
#define N 1001
char bit[N][126];//punct][dreapta
int a[N],b[N],c[N],x[N],y[N],mark[N];
int compare(char a[],char b[],int n)
{int i;
 for (i=0;i<n;i++)
 {if(a[i]!=b[i])return 0;
 }
 return 1;
}
int main ()
{int n,m,i,j,p,q,a2,b2,c2,nr;
 freopen("regiuni.in","r",stdin);
 freopen("regiuni.out","w",stdout);
 scanf("%d%d",&n,&m);
 for (i=1;i<=n;i++)
 {scanf("%d %d %d",&a[i],&b[i],&c[i]);
 }
 for (i=1;i<=m;i++)
 {scanf("%d %d",&x[i],&y[i]);
 }
 for (i=1;i<=n;i++) //drepte
 {p=i/8;q=i%8;
  if(a[i]!=0)
  {a2=a[i];b2=b[i];c2=c[i];
   for (j=1;j<=m;j++) //puncte
   {if((-c2-b2*y[j])/a2<x[j])
    {bit[j][p]=1<<q;
    }
   }
  }
  else
  {a2=a[i];b2=b[i];c2=c[i];
   for (j=1;j<=m;j++) //puncte
   {if((-c2-a2*x[j])/b2<y[j])
    {bit[j][p]=1<<q;
    }
   }
  }
 }

 for (i=1,nr=0;i<m;i++)
 {if(mark[i]==0)
  {mark[i]=1;
   nr++;
   for (j=i+1;j<=m;j++)
   {if(mark[j]==0&&compare(bit[i],bit[j],n/8+1)==1)
    {mark[j]=1;
    }
   }
  }
 }
 printf("%d",nr);
 return 0;
}