Cod sursa(job #926228)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 25 martie 2013 08:08:25
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
 
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;
}
 
void Solve() {
    for (int i = 0; i < N; ++i) {
        int x, y; scanf("%d %d", &x, &y);
        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);
                for (; Hash[h][i] >= U[h]; Hash[h][i] -= U[h]);
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        int NewGroup = 1;
        for (int j = i - 1; j >= 0 && NewGroup != 0; --j)
            if (Equal(i, j))
                NewGroup = 0;
        Regions += NewGroup;
    }
}
 
void Read() {
    freopen("regiuni.in", "r", stdin);
    scanf("%d %d", &M, &N);
    for (int i = 0; i < M; ++i)
        scanf("%d %d %d", &A[i], &B[i], &C[i]);
}
 
void Print() {
    freopen("regiuni.out", "w", stdout);
    printf("%d\n", Regions);
}
 
int main() {
    Read();
    Solve();
    Print();
    return 0;
}