Cod sursa(job #1474698)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 22 august 2015 16:48:17
Problema Regiuni Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 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;
using Point = pair < short, short >;
using Line = tuple < short, short, short >;

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

inline int getSide(Point P, Line L) {
    if(get<0>(L) * get<0>(P) + get<1>(L) * get<1>(P) + get<2>(L) < 0) return -1;
    else return 1;
}

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

    in >> n >> m;
    for(i = 1; i <= n; i++) {
        in >> a >> b >> c;
        L[i] = make_tuple(a, b, c);
    }
    for(i = 1; i <= m; i++) {
        in >> a >> b;
        G[1].push_back(make_pair(a, b));
    }
    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;
}