Cod sursa(job #1891672)

Utilizator EpictetStamatin Cristian Epictet Data 24 februarie 2017 11:18:41
Problema Regiuni Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <fstream>
#include <vector>

using namespace std;

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

class dreapta { public : int a, b, c; } N[1010];
class punct { public : int x, y; } M[1010];
int n, m, g = 1;
vector < int > Plus, Minus, V[10010];

int Pos(punct p, dreapta d)
{
    return (d.a * p.x + d.b * p.y + d.c);
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        fin >> N[i].a >> N[i].b >> N[i].c;
    }
    for (int i = 1; i <= m; i ++)
    {
        fin >> M[i].x >> M[i].y;
        V[g].push_back(i);
    }
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1, jj = g; j <= jj; j ++)
        {
            if (V[j].size() <= 1) continue;
            while (!Plus.empty()) Plus.pop_back();
            while (!Minus.empty()) Minus.pop_back();
            for (vector < int > :: iterator it = V[j].begin(); it != V[j].end(); it ++)
            {
                if (Pos(M[*it], N[i]) > 0) Plus.push_back(*it);
                else Minus.push_back(*it);
            }
            if (Plus.size() && Minus.size())
            {
                g ++;
                if (Plus.size() < Minus.size())
                {
                    for (vector < int > :: iterator it1 = V[j].begin(), it2 = Plus.begin(); it1 != V[j].end() && it2 != Plus.end(); it1 ++)
                    {
                        if (*it1 == *it2)
                        {
                            swap(*it1, V[j].back());
                            V[j].pop_back();
                            V[g].push_back(*it2);
                            it2 ++;
                        }
                    }
                }
                else
                {
                    for (vector < int > :: iterator it1 = V[j].begin(), it2 = Minus.begin(); it1 != V[j].end() && it2 != Minus.end(); it1 ++)
                    {
                        if (*it1 == *it2)
                        {
                            swap(*it1, V[j].back());
                            V[j].pop_back();
                            V[g].push_back(*it2);
                            it2 ++;
                        }
                    }
                }
            }
        }
    }
    fout << g << '\n';
    fout.close();
    return 0;
}