Cod sursa(job #1592730)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 7 februarie 2016 21:35:19
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <vector>

const int DIM = 1 << 10;
const int MOD = 32767;
const int MOD1 = 100009;
const int MOD2 = 666013;
const int VAL1 = 23;
const int VAL2 = 29;
using namespace std;

int N, M, x, y, answer, value1, value2;
struct point {int a, b, c;} P[DIM];
struct hash_value {int x, y;};
vector <hash_value> Hash[MOD];

hash_value make_hash( int x, int y ) {
    hash_value my_hash = {x, y};
    return my_hash;
}

void add_hash( hash_value value ) {
    int pos = (value.x * value.y) % MOD;

    for( int i = 0; i < Hash[pos].size(); i ++ )
        if( Hash[pos][i].x == value.x && Hash[pos][i].y == value.y )
            return;

    Hash[pos].push_back( value );
}

bool which_part( int x, int y, int p ) {
    return P[p].a * x + P[p].b * y + P[p].c > 0;
}

int main () {

    freopen( "regiuni.in" , "r", stdin  );
    freopen( "regiuni.out", "w", stdout );

    scanf( "%d %d", &N, &M );
    for( int i = 1; i <= N; i ++ )
        scanf( "%d %d %d", &P[i].a, &P[i].b, &P[i].c );

    for( int i = 1; i <= M; i ++ ) {
        scanf( "%d %d", &x, &y );
        value1 = value2 = 0;

        for( int j = 1; j <= N; j ++ ) {
            value1 = (value1 * VAL1 + which_part(x, y, j)) % MOD1;
            value2 = (value2 * VAL2 + which_part(x, y, j)) % MOD2;
        }

        add_hash( make_hash( value1, value2 ) );
    }

    for( int i = 0; i < MOD; i ++ )
        answer += Hash[i].size();
    printf( "%d\n", answer );

    return 0;
}