Cod sursa(job #3233337)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 23:44:03
Problema Regiuni Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct UnionFind {
    vector<int> parent, rank;

    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int u) {
        if (parent[u] != u) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    void unite(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
};

int main() {
    ifstream infile("regiuni.in");
    ofstream outfile("regiuni.out");

    int n, m;
    infile >> n >> m;

    vector<tuple<int, int, int>> lines(n);
    for (int i = 0; i < n; ++i) {
        int a, b, c;
        infile >> a >> b >> c;
        lines[i] = make_tuple(a, b, c);
    }

    vector<pair<int, int>> points(m);
    for (int i = 0; i < m; ++i) {
        int x, y;
        infile >> x >> y;
        points[i] = make_pair(x, y);
    }

    UnionFind uf(m);

    for (int i = 0; i < m; ++i) {
        for (int j = i + 1; j < m; ++j) {
            bool sameRegion = true;
            for (int k = 0; k < n; ++k) {
                int a, b, c;
                tie(a, b, c) = lines[k];
                int sign1 = a * points[i].first + b * points[i].second + c;
                int sign2 = a * points[j].first + b * points[j].second + c;
                if ((sign1 < 0 && sign2 > 0) || (sign1 > 0 && sign2 < 0)) {
                    sameRegion = false;
                    break;
                }
            }
            if (sameRegion) {
                uf.unite(i, j);
            }
        }
    }

    int numRegions = 0;
    vector<bool> visited(m, false);
    for (int i = 0; i < m; ++i) {
        int root = uf.find(i);
        if (!visited[root]) {
            visited[root] = true;
            numRegions++;
        }
    }

    outfile << numRegions << endl;

    infile.close();
    outfile.close();

    return 0;
}