Cod sursa(job #986101)

Utilizator geniucosOncescu Costin geniucos Data 17 august 2013 18:07:12
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int nr,v,i,j,n,m,bt,nn,ind[1009],A[1009],B[1009],C[1009],x[1009],y[1009];
long long val,a[1003][19];
bool cmp(int p1,int p2)
{
    int i;
    for(i=1;i<=nn;i++)
        if(a[p1][i]!=a[p2][i]) break;
    return (a[p1][i]<=a[p2][i]);
}
bool eg(int p1,int p2)
{
    int i;
    for(i=1;i<=nn;i++)
        if(a[i][p1]!=a[i][p2]) break;
    return (i>nn);
}
int main()
{
freopen("regiuni.in","r",stdin);
freopen("regiuni.out","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
for(i=1;i<=n;i++)
{
    scanf("%d",&A[i]);
    scanf("%d",&B[i]);
    scanf("%d",&C[i]);
}
for(i=1;i<=m;i++)
{
    scanf("%d",&x[i]);
    scanf("%d",&y[i]);
    nn=0;
    bt=-1;
    val=0;
    for(j=1;j<=n;j++)
    {
        v=(x[i]*A[j]+y[i]*B[j]+C[j]>0);
        bt++;
        if(bt==61)
        {
            nn++;
            a[i][nn]=val;
            bt=0;
            val=0;
            if(v) val+=1LL<<bt;
        }
        else val+=(1LL<<bt)*v;
    }
    if(n%60!=0)
    {
        nn++;
        a[i][nn]=val;
    }
    ind[i]=i;
}
sort(ind+1,ind+m+1,cmp);
nr=1;
for(i=2;i<=m;i++)
    if(!eg(ind[i-1],ind[i])) nr++;
printf("%d\n",nr);
return 0;
}