Cod sursa(job #40393)

Utilizator victorsbVictor Rusu victorsb Data 27 martie 2007 13:39:40
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 1024
#define Tmax 12289
#define r 98317
#define a first
#define b second.first
#define c second.second
#define x first
#define y second
#define pb push_back
#define sz size()

int n, m, ct;
pair<int, pair<int, int> > dr[Nmax];
pair<int, int> punct[Nmax];
int T[Tmax], v[Nmax];

void citire()
{
    int i;
    
    scanf("%d %d\n", &n, &m);
    
    for (i = 1; i <= n; ++i)
        scanf("%d %d %d\n", &dr[i].a, &dr[i].b, &dr[i].c);
    
    for (i = 1; i <= m; ++i)
        scanf("%d %d\n", &punct[i].x, &punct[i].y);
}

void solve()
{
    int i, j, hash, ct = 0;
    
    for (i = 1; i <= m; ++i)
    {
        for (j = 1; j <= n; ++j)
            if (dr[j].a * punct[i].x + dr[j].b * punct[i].y + dr[j].c > 0)
                v[j] = 1;
            else
                v[j] = 0;
        
        hash = 0;
        
        for (j = 1; j <= m; ++j)
        {
            hash = hash * r + v[j] * j * j;
            hash %= Tmax;
        }
        
        if (!T[hash])
        {
            T[hash] = 1;
            ++ct;
        }
    }
    
    printf("%d\n", ct);
}

int main()
{
    freopen("regiuni.in", "r", stdin);
    freopen("regiuni.out", "w", stdout);
    citire();
    solve();
    return 0;
}