Cod sursa(job #3256980)

Utilizator Mitrut_SebeniSebeni Mitrut Gabriel Mitrut_Sebeni Data 16 noiembrie 2024 13:02:37
Problema Regiuni Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

int main() {
    // Deschiderea fișierelor de intrare și ieșire
    ifstream in("regiuni.in");
    ofstream out("regiuni.out");

    int n, m;
    in >> n >> m;

    vector<vector<int>> drepte(n, vector<int>(3)); // a, b, c pentru fiecare dreaptă
    for (int i = 0; i < n; i++) {
        in >> drepte[i][0] >> drepte[i][1] >> drepte[i][2];
    }

    vector<pair<int, int>> puncte(m); // coordonatele punctelor
    for (int i = 0; i < m; i++) {
        in >> puncte[i].first >> puncte[i].second;
    }

    set<vector<int>> grupuri; // set de semnături unice

    // Pentru fiecare punct, calculăm semnătura față de fiecare dreaptă
    for (int i = 0; i < m; i++) {
        int x = puncte[i].first;
        int y = puncte[i].second;

        vector<int> semnatura;

        for (int j = 0; j < n; j++) {
            int a = drepte[j][0];
            int b = drepte[j][1];
            int c = drepte[j][2];

            int valoare = a * x + b * y + c;

            if (valoare > 0) {
                semnatura.push_back(1); // punctul este de o parte a dreptei
            } else {
                semnatura.push_back(-1); // punctul este de cealaltă parte a dreptei
            }
        }

        // Adăugăm semnătura punctului în set
        grupuri.insert(semnatura);
    }

    // Răspunsul este numărul de semnături distincte
    out << grupuri.size() << endl;

    return 0;
}