Cod sursa(job #866501)

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

using namespace std;

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

struct Point {
    int x, y;

    Point() {}

    Point(int x, int y) {
        this->x = x, this->y = y;
    }
};

struct Line {
    int a, b, c;

    Line() {}

    Line(int a, int b, int c) {
        this->a = a, this->b = b, this->c = c;
    }

    int Side(Point p) const {
        return (a * p.x + b * p.y + c >= 0 ? 1 : 0);
    }
};

Point P[MaxN];
Line L[MaxN];
int N, M, Index[MaxN], Hash[NU][MaxN], Regions;

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)
        for (int h = 0; h < NU; ++h)
            for (int j = 0; j < M; ++j)
                Hash[h][i] = (Base * Hash[h][i] + L[j].Side(P[i])) % U[h];
    for (int i = 0; i < N; ++i)
        Index[i] = i;
    sort(Index, Index + N, Compare);
    Regions = 1;
    for (int i = 1; i < N; ++i)
        if (!Equal(Index[i - 1], Index[i]))
            ++Regions;
}

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", &L[i].a, &L[i].b, &L[i].c) == 3);
    for (int i = 0; i < N; ++i)
        assert(scanf("%d %d", &P[i].x, &P[i].y) == 2);
}

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

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