Cod sursa(job #866497)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 28 ianuarie 2013 10:57:46
Problema Regiuni Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int Base = 2;
const int U = 666013;

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);
    }
};

vector<Point> P;
vector<Line> L;
vector<int> Region;

void Solve() {
    for (size_t i = 0; i < P.size(); ++i)
        for (size_t j = 0; j < L.size(); ++j)
            Region[i] = (Base * Region[i] + L[j].Side(P[i])) % U;
    sort(Region.begin(), Region.end());
    Region.erase(unique(Region.begin(), Region.end()), Region.end());
}

void Read() {
    freopen("regiuni.in", "r", stdin);
    int M, N; scanf("%d %d", &M, &N);
    for (int i = 0; i < M; ++i) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        L.push_back(Line(a, b, c));
    }
    for (int i = 0; i < N; ++i) {
        int x, y; scanf("%d %d", &x, &y);
        P.push_back(Point(x, y)), Region.push_back(0);
    }
}

void Print() {
    freopen("regiuni.out", "w", stdout);
    printf("%d\n", static_cast<int>(Region.size()));
}

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