Cod sursa(job #384692)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 20 ianuarie 2010 18:40:27
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>

#define MOD 666013
#define MOD2 809171

int h1[1005],h2[1005],n,m,reg;
struct dreapta
{
    int a,b,c;
};
dreapta v[1003];
int semiplan(int a, int b, int c, int x, int y)
{
    int E = a * x + b * y + c;
    if (E > 0) return +1;
    if (E < 0) return -1;
    return 0;
}

int f(int x, int y, int baza, int rest)
{
    int i;
    int r=0,val;
    for(i=1;i<=n;i++)
    {
        val=semiplan(v[i].a,v[i].b,v[i].c,x,y);
        r=(r*baza+val)%rest;
    }
    return r;
}

int main ()
{
    int x,y,i,j;
    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",&v[i].a,&v[i].b,&v[i].c);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        h1[i]=f(x,y,2,MOD);
        h2[i]=f(x,y,7,MOD2);
        for(j=1;j<i;j++)
            if(h1[i]==h1[j] && h2[i]==h2[j])
                break;
        if(j!=i)
            reg++;
    }
    printf("%d\n",reg+1);
    return 0;
}