Cod sursa(job #1392011)

Utilizator ericptsStavarache Petru Eric ericpts Data 18 martie 2015 12:31:01
Problema Regiuni Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#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<int> group;

deque<group> v;

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

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

bool cross(const point &P, const line &L) {
    double xp1 = 0,
    yp1 = - 1.0 * L.c / L.b;

    double xp2 = - 1.0 * L.c / L.a,
    yp2 = 0;

    double x1 = xp2 - xp1,
    y1 = yp2 - yp1;

    double x2 = P.x - xp2,
    y2 = P.y - yp2;

    return (x1 * y2 - x2 * y1) < 0;
}

bool left(const point &P, const line &L) {
    if(L.b == 0) {
        return P.x < (-1.0 * L.c / L.a);
    } else if(L.a == 0) {
        return P.y > (-1.0 * L.c / L.b);
    } else {
        return cross(P, L);
    }
}

void consider(int w) {
    group L, R;
    for(int i = 0 ; i < (int)v.size() ; ++i) {
        const group &now = v.front();
        L.clear();
        R.clear();

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

        v.pop_front();

        if(!L.empty())
            v.pb(L);
        if(!R.empty())
            v.pb(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.pb(now);

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

    ofstream out("regiuni.out");
    out << v.size() << "\n";
    out.close();
    in.close();

    return 0;
}