Cod sursa(job #1839051)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 2 ianuarie 2017 13:11:00
Problema Regiuni Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define MAXN 1050

using namespace std;

struct dreapta
{
    int a, b, c;
};
dreapta dr[MAXN];
struct punct
{
    int x, y;
};
punct p[MAXN];

bool parte(punct e, dreapta d)
{
    return (e.x*d.a + e.y*d.b + d.c) > 0;
}

int n, m;
queue<vector<int> > q;
void solve()
{
    vector<int> prim;
    for (int i = 1; i <= m; i++)
        prim.push_back(i);
    q.push(prim);
    for (int i = 1; i <= n; i++) {
        for (int j = q.size(); j > 0; j--) {
            vector<int> trig, clo;
            vector<int> vp = q.front();
            q.pop();
            for (int ind : vp) {
                if (parte(p[ind], dr[i]))
                    trig.push_back(ind);
                else
                    clo.push_back(ind);
            }
            if (trig.size()) q.push(trig);
            if (clo.size()) q.push(clo);
        }
    }
}

int main()
{
    freopen("regiuni.in", "r", stdin);
    freopen("regiuni.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d", &dr[i].a, &dr[i].b, &dr[i].c);
    for (int i = 1; i <= m; i++)
        scanf("%d %d", &p[i].x, &p[i].y);
    solve();
    printf("%d", q.size());

    return 0;
}