Cod sursa(job #1392065)

Utilizator ericptsStavarache Petru Eric ericpts Data 18 martie 2015 12:51:27
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

#define pb push_back

struct line{
    int a, b, c;
};

struct point {
    int x, y;
};


const int MAX_N = 1000 + 1;
const int MAX_M = 1000 + 1;

line l[MAX_N];
point p[MAX_M];

int n, m;

typedef vector<short int> group;

group v[MAX_N];
int lo, hi;

void showGroup(group A) {
    for(int i = 0 ; i < (int)A.size() ; ++i) {
        cout << A[i] << " ";
    }
    cout << "\n";
}

void showGroups() {
    for(int i = lo ; i <= hi ; ++i)
        showGroup(v[i]);
    cout << "\n\n\n\n";
}

bool left(const point &P, const line &L) {
    return (P.x * L.a + P.y * L.b + L.c) > 0;
}

group R;

bool bad[MAX_N];

void removeBad(group &v) {
    int n = v.size() - 1;

    for(int i = n ; i >= 0 ; --i) {
        if(bad[i]) {
            v[i] = v[n];
            v.pop_back();
        }
    }

}

void consider(int w) {
    for(int i = lo ; i <= hi ; ++i) {
        group &now = v[i];

        R.clear();

        for(int i = 0 ; i < (int)now.size() ; ++i) {
            const int pt = now[i];
            bad[i] = 0;
            if(!left(p[pt], l[w])) {
                R.pb(pt);
                bad[i] = 1;
            }
        }

        removeBad(now);

        if(now.empty())
            swap(now, R);

        if(!R.empty())
            v[++hi] = R;
    }

    //showGroups();
}

int main() {
    ifstream in("regiuni.in");
    in >> n >> m;

    for(int i = 1 ; i <= n ; ++i) {
        in >> l[i].a >> l[i].b >> l[i].c;
    }
    group now;
    for(int i = 1 ; i <= m ; ++i) {
        in >> p[i].x >> p[i].y;
        now.pb(i);
    }
    v[0] = now;
    lo = hi = 0;

    for(int i = 1 ; i <= n ; ++i)
        consider(i);

    ofstream out("regiuni.out");
    out << (hi - lo + 1) << "\n";
    out.close();
    in.close();

    return 0;
}