Cod sursa(job #481795)

Utilizator vladiiIonescu Vlad vladii Data 1 septembrie 2010 18:19:37
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define maxn 1024
#define P1 11
#define P2 17
#define mod1 33789
#define mod2 27891

int N, M, reg;
int Q[maxn], hash1[maxn], hash2[maxn];
struct Drepte {
    int a, b, c;
} D[maxn];

int cmp(int i, int j) {
    if(hash1[i] != hash1[j]) {
         return hash1[i] < hash1[j];
    }
    return hash2[i] < hash2[j];
}

int main() {
    FILE *f1=fopen("regiuni.in", "r"), *f2=fopen("regiuni.out", "w");
    int i, j, p, x, y;

    fscanf(f1, "%d %d\n", &N, &M);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d %d %d\n", &D[i].a, &D[i].b, &D[i].c);
    }
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d\n", &x, &y);
         for(j=1; j<=N; j++) {
              p = D[j].a * x + D[j].b * y + D[j].c;
              if(p > 0) p = 1;
              else p = 0;
              hash1[i] = (hash1[i] * P1 + p) % mod1;
              hash2[i] = (hash2[i] * P2 + p) % mod2;
         }
         Q[i] = i;
    }

    sort(Q+1, Q+M+1, cmp);

    int lst = 0;
    for(i=1; i<=M; i++) {
         if(hash1[i] == hash1[lst] && hash2[i] == hash2[lst]) {
              reg++;
         }
         else {
              lst = i;
         }
    }
    if(lst != M) reg++;

    fprintf(f2, "%d\n", reg);
    fclose(f1); fclose(f2);
    return 0;
}