Cod sursa(job #866505)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 28 ianuarie 2013 11:17:42
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <cassert>

using namespace std;

const int Base = 2;
const int NU = 2;
const int U[] = {666013, 1000003};
const int MaxN = 1005;

int M, A[MaxN], B[MaxN], C[MaxN];
int N, Hash[NU][MaxN], Regions;

inline int Side(const int L, const int x, const int y) {
    return (A[L] * x + B[L] * y + C[L] >= 0 ? 1 : 0);
}

inline bool Equal(const int a, const int b) {
    for (int h = 0; h < NU; ++h)
        if (Hash[h][a] != Hash[h][b])
            return false;
    return true;
}

inline bool Compare(const int a, const int b) {
    for (int h = 0; h < NU; ++h)
        if (Hash[h][a] != Hash[h][b])
            return Hash[h][a] < Hash[h][b];
    return false;
}

void Solve() {
    for (int i = 0; i < N; ++i) {
        int x, y; assert(scanf("%d %d", &x, &y) == 2);
        for (int h = 0; h < NU; ++h)
            for (int j = 0; j < M; ++j)
                Hash[h][i] = (Base * Hash[h][i] + Side(j, x, y)) % U[h];
    }
    for (int i = 0; i < N; ++i) {
        int NewGroup = 1;
        for (int j = i - 1; j >= 0 && NewGroup; --j)
            if (Equal(i, j))
                NewGroup = 0;
        Regions += NewGroup;
    }
}

void Read() {
    assert(freopen("regiuni.in", "r", stdin));
    assert(scanf("%d %d", &M, &N) == 2);
    for (int i = 0; i < M; ++i)
        assert(scanf("%d %d %d", &A[i], &B[i], &C[i]) == 3);
}

void Print() {
    assert(freopen("regiuni.out", "w", stdout));
    printf("%d\n", Regions);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}