Cod sursa(job #1774777)

Utilizator enacheionutEnache Ionut enacheionut Data 9 octombrie 2016 14:13:34
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <unordered_set>
#include <vector>
#include <bitset>

#define MAX 1010

using namespace std;

struct Dreapta
{
    int a;
    int b;
    int c;
};

struct Punct
{
    int x;
    int y;
};

int CalculeazaEcuatiaDreptei(const Dreapta dreapta, const Punct punct)
{
    return dreapta.a * punct.x + dreapta.b * punct.y + dreapta.c;
}

void ReadInput(vector<Dreapta> &drepte, vector<Punct> &puncte, ifstream &in)
{
    for(auto& d : drepte)
    {
        in >> d.a >> d.b >> d.c;
    }

    for(auto& p : puncte)
    {
        in >> p.x >> p.y;
    }
}

vector<bitset<MAX>> CalculeazaRegiuneaFiecaruiPunct( vector<Dreapta> drepte, int numarDrepte,
                                                    vector<Punct> puncte, int numarPuncte )
{
    vector<bitset<MAX>> car(numarPuncte, 0);
    for(int j = 0; j < numarPuncte; ++j)
    {
        for(int i = 0; i < numarDrepte; ++i)
        {
            car[j][i] = ( CalculeazaEcuatiaDreptei(drepte[i], puncte[j]) > 0 );
        }
    }

    return car;
}

int CalculeazaNumarulDeRegiuni(vector<bitset<MAX>> regiuniPuncte)
{
    unordered_set<bitset<MAX>> regiuni;
    regiuni.insert(regiuniPuncte.begin(), regiuniPuncte.end());

    return regiuni.size();
}

int main()
{
    int numarDrepte;
    int numarPuncte;

    ifstream in("regiuni.in");

    in >> numarDrepte >> numarPuncte;
    vector<Dreapta> drepte(numarDrepte);
    vector<Punct> puncte(numarPuncte);

    ReadInput(drepte, puncte, in);
    in.close();

    auto regiuniPuncte = CalculeazaRegiuneaFiecaruiPunct( drepte, numarDrepte, puncte, numarPuncte );

    ofstream out("regiuni.out");
    out << CalculeazaNumarulDeRegiuni(regiuniPuncte);
    out.close();

    return 0;
}