Cod sursa(job #866491)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 28 ianuarie 2013 10:42:20
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>

using namespace std;

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< vector<Point> > Regions;
vector<Line> L;

void Solve() {
    for (size_t i = 0; i < L.size(); ++i) {
        vector< vector<Point> > NewRegions;
        for (size_t r = 0; r < Regions.size(); ++r) {
            vector<Point> Sides[2];
            for (size_t p = 0; p < Regions[r].size(); ++p)
                Sides[L[i].Side(Regions[r][p])].push_back(Regions[r][p]);
            for (int s = 0; s < 2; ++s)
                if (!Sides[s].empty())
                    NewRegions.push_back(Sides[s]);
        }
        Regions = NewRegions;
    }
}

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

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

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