Cod sursa(job #40986)

Utilizator victorsbVictor Rusu victorsb Data 27 martie 2007 21:28:01
Problema Regiuni Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define Nmax 1024
#define Tmax 1543
#define r1 951753153
#define r2 153957159
#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<short, pair<short, short> > dr[Nmax];
pair<short, short> punct[Nmax];
char v[Nmax];
vector<short> T[Tmax];

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

int find(int hash1, int hash2)
{
    int i;
    
    for (i = 0; i < T[hash1].sz; ++i)
        if (T[hash1][i] == hash2)
            return 1;
    
    return 0;
}

void solve()
{
    int i, j, hash1, ct = 0, hash2;
    
    for (i = 1; i <= m; ++i)
    {
        for (j = 1; j <= n; ++j)
            if ((int)dr[j].a * punct[i].x + dr[j].b * punct[i].y + dr[j].c > 0)
                v[j] = 1;
            else
                v[j] = 0;
        
        hash1 = hash2 = 0;
        
        for (j = 1; j <= n; ++j)
        {
            hash1 = ((hash1 << 6) ^ (hash1 >> 16) - hash1) + (v[j] * r2);
            hash2 = ((hash2 << 5) + hash2) + v[j] * r1 * j * j * j;
        }
        
        hash1 = abs(hash1) % Tmax;
        hash2 = abs(hash2 + hash2 >> 16) % Nmax;
        
        //printf("%d %d\n", hash1, hash2);
        
        if (!find(hash1, hash2))
        {
            T[hash1].pb(hash2);
            ++ct;
        }
    }
    
    printf("%d\n", ct);
}

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