Cod sursa(job #1533905)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 23 noiembrie 2015 08:00:41
Problema Regiuni Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <vector>
#include <tuple>

using namespace std;

ifstream in("regiuni.in");
ofstream out("regiuni.out");

const int MAX_G = 1000;
const int MAX_L = 1000;

struct Point {
    short x;
    short y;
};

struct Line {
    short a;
    short b;
    short c;
};

int nGroups = 1;
vector < Point > G[MAX_G + 1];
Line L[MAX_L + 1];

inline int getSide(Point P, Line L) {
    if(1LL * L.a * P.x + L.b * P.y + L.c < 0) return -1;
    else return 1;
}

int main() {
    int i, j, k, n, m, a, b, c, initNG;
    bool found1, found_neg1;
    Point P;

    in >> n >> m;
    for(i = 1; i <= n; i++) {
        in >> L[i].a >> L[i].b >> L[i].c;
    }
    for(i = 1; i <= m; i++) {
        in >> P.x >> P.y;
        G[1].push_back(P);
    }
    for(i = 1; i <= n; i++) {
        initNG = nGroups;
        for(j = 1; j <= initNG; j++) {
            found1 = found_neg1 = 0;
            for(k = 0; k < G[j].size(); k++) {
                if(getSide(G[j][k], L[i]) == -1) found_neg1 = 1;
                else found1 = 1;
            }
            if(found_neg1 * found1 != 0) {
                nGroups++;
                for(k = G[j].size() - 1; k >= 0; k--) {
                    if(getSide(G[j][k], L[i]) == -1) {
                        G[nGroups].push_back(G[j][k]);
                        swap(G[j][k], G[j][G[j].size() - 1]);
                        G[j].pop_back();
                    }
                }
            }
        }
    }

    out << nGroups;
    return 0;
}