Cod sursa(job #1891614)

Utilizator BugirosRobert Bugiros Data 24 februarie 2017 10:41:59
Problema Regiuni Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

const int MAXN = 1000;


struct punct
{
    int x,y;
};

struct dreapta
{
    int a,b,c;
    int parte(punct p)
    {
        int nr = a * p.x + b * p.y + c;
        if (nr < 0)
            return -1;
        else return 1;
    }
};


int n,m;

dreapta drepte[MAXN];

vector<vector<punct>*> grupe;

void citire()
{
    in >> n >> m;
    for (int i = 1;i <= n;++i)
        in >> drepte[i].a >> drepte[i].b >> drepte[i].c;
    grupe.push_back(new vector<punct>);
    for (int i = 1;i <= m;++i)
    {
        int x,y;
        in >> x >> y;
        grupe[0]-> push_back((punct){x,y});
    }
}

void prelucrare()
{
    for (int dr = 1;dr <= n;++dr)
    {
        unsigned int lim = grupe.size();
        for (unsigned int i = 0;i < lim;++i)
        //separare grupa in doua in functie de partea pe care punctele sunt pe dreapta
        {
            vector<punct>* grupa_1 = new vector<punct>;
            vector<punct>* grupa_2 = new vector<punct>;
            for (unsigned int j = 0;j < grupe[i]->size();++j)
            {
                punct p = (*grupe[i])[j];
                if (drepte[dr].parte(p) == -1)
                    grupa_1->push_back(p);
                else grupa_2->push_back(p);
            }
            delete grupe[i];
            grupe[i] = grupa_1;
            grupe.push_back(grupa_2);
        }
        for (unsigned int i = 0;i < grupe.size();++i)
        {
            if (grupe[i]->size() == 0)
            {
                delete grupe[i];
                grupe[i] = NULL;
            }
        }
        unsigned int cursor = 0;
        for (unsigned int i = 0;i < grupe.size();++i)
        {
             if (grupe[i] != NULL)
             {
                grupe[cursor] = grupe[i];
                ++cursor;
             }
        }
        grupe.resize(cursor);
    }
}

int main()
{
    citire();
    prelucrare();
    out << grupe.size() << '\n';
    return 0;
}