Cod sursa(job #478804)

Utilizator freak93Adrian Budau freak93 Data 20 august 2010 14:04:26
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<cstdio>

using namespace std;

const char iname[]="regiuni.in";
const char oname[]="regiuni.out";
const int maxn=1024;
const int p1=3;
const int p2=5;
const int q1=1000000007;
const int q2=1000000009;

int hash1[maxn],hash2[maxn],d[maxn][3],i,j,n,m,rez,x,y;

int main()
{
    freopen(iname,"r",stdin);
    freopen(oname,"w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
        scanf("%d%d%d",&d[i][0],&d[i][1],&d[i][2]);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        for(j=1;j<=n;++j)
            if(x*d[j][0]+y*d[j][1]+d[j][2]>0)
                hash1[i]=(hash1[i]*p1+1)%q1,hash2[i]=(hash2[i]*p2+2)%q2;
            else
                hash1[i]=(hash1[i]*p1+2)%q1,hash2[i]=(hash2[i]*p2+3)%q2;
    }
    rez=1;
    for(i=2;i<=m;++i)
    {
        for(j=1;j<i;++j)
            if(hash1[i]==hash1[j]&&hash2[i]==hash2[j])
                break;
        if(j==i)
            ++rez;
    }
    printf("%d\n",rez);
}