Pagini recente » Cod sursa (job #318227) | Cod sursa (job #290996) | Cod sursa (job #1419685) | Cod sursa (job #2522822) | Cod sursa (job #3233337)
#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;
}