Cod sursa(job #39928)

Utilizator astronomyAirinei Adrian astronomy Data 27 martie 2007 09:26:01
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAXN 1024
#define MOD 10000003

typedef struct dreapta { short int a, b, c; } dreapta;
typedef struct point { short int x, y; } point;

int N, M, res, hash[MAXN];
dreapta D[MAXN];
point P[MAXN];

int F(dreapta d, point p)
{
    int t = (int)d.a*p.x+(int)d.b*p.y+(int)d.c;
    return t > 0 ? 1 : -1;
}

void solve(void)
{
    int i, j, key, sgn, last = -1;

    for(i = 1; i <= M; i++)
    {
        for(key = 0, j = 1; j <= N; j++)
        {
            sgn = F(D[j], P[i]);
            if(sgn == 1)
                key = (key*2+1) % MOD;
            else
                key = (key*2+0) % MOD;
        }
        hash[i] = key;
    }

    sort(hash+1, hash+M+1);
    for(i = 1; i <= M; i++)
    {
        if(hash[i] != last)
            res++, last = hash[i];
    }
}

void read_data(void)
{
    int i, j;

    scanf("%d %d\n", &N, &M);

    for(i = 1; i <= N; i++)
        scanf("%d %d %d\n", &D[i].a, &D[i].b, &D[i].c);

    for(i = 1; i <= M; i++)
        scanf("%d %d\n", &P[i].x, &P[i].y);
}

void write_data(void)
{
    printf("%d\n", res);
}

int main(void)
{
    freopen("regiuni.in", "rt", stdin);
    freopen("regiuni.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}