Pagini recente » Cod sursa (job #2400675) | Cod sursa (job #915849) | Cod sursa (job #292519) | Cod sursa (job #2686760) | Cod sursa (job #1474701)
#include <fstream>
#include <vector>
#include <tuple>
using namespace std;
ifstream in("regiuni.in");
ofstream out("regiuni.out");
const int MAX_G = 1000;
const int MAX_L = 1000;
struct Point {
short x;
short y;
};
struct Line {
short a;
short b;
short c;
};
short nGroups = 1;
vector < Point > G[MAX_G + 1];
Line L[MAX_L + 1];
inline int getSide(Point P, Line L) {
if(1LL * L.a * P.x + 1LL * L.b * P.y + 1LL * L.c < 0) return -1;
else return 1;
}
int main() {
int i, j, k, n, m, a, b, c, initNG;
bool found1, found_neg1;
in >> n >> m;
for(i = 1; i <= n; i++) {
in >> L[i].a >> L[i].b >> L[i].c;
}
for(i = 1; i <= m; i++) {
in >> a >> b;
G[1].push_back({a, b});
}
for(i = 1; i <= n; i++) {
initNG = nGroups;
for(j = 1; j <= initNG; j++) {
found1 = found_neg1 = 0;
for(k = 0; k < G[j].size(); k++) {
if(getSide(G[j][k], L[i]) == -1) found_neg1 = 1;
else found1 = 1;
}
if(found_neg1 * found1 != 0) {
nGroups++;
for(k = G[j].size() - 1; k >= 0; k--) {
if(getSide(G[j][k], L[i]) == -1) {
G[nGroups].push_back(G[j][k]);
swap(G[j][k], G[j][G[j].size() - 1]);
G[j].pop_back();
}
}
}
}
}
out << nGroups;
return 0;
}