Pagini recente » Profil ileana20 | Cod sursa (job #71566) | Cod sursa (job #393952) | Istoria paginii utilizator/flavianeacsu | Cod sursa (job #866491)
Cod sursa(job #866491)
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
struct Point {
int x, y;
Point() {}
Point(int x, int y) {
this->x = x, this->y = y;
}
};
struct Line {
int a, b, c;
Line() {}
Line(int a, int b, int c) {
this->a = a, this->b = b, this->c = c;
}
int Side(Point p) const {
return (a * p.x + b * p.y + c >= 0 ? 1 : 0);
}
};
vector< vector<Point> > Regions;
vector<Line> L;
void Solve() {
for (size_t i = 0; i < L.size(); ++i) {
vector< vector<Point> > NewRegions;
for (size_t r = 0; r < Regions.size(); ++r) {
vector<Point> Sides[2];
for (size_t p = 0; p < Regions[r].size(); ++p)
Sides[L[i].Side(Regions[r][p])].push_back(Regions[r][p]);
for (int s = 0; s < 2; ++s)
if (!Sides[s].empty())
NewRegions.push_back(Sides[s]);
}
Regions = NewRegions;
}
}
void Read() {
assert(freopen("regiuni.in", "r", stdin));
int M, N; assert(scanf("%d %d", &M, &N) == 2);
for (int i = 0; i < M; ++i) {
int a, b, c; assert(scanf("%d %d %d", &a, &b, &c) == 3);
L.push_back(Line(a, b, c));
}
vector<Point> P;
for (int i = 0; i < N; ++i) {
int x, y; assert(scanf("%d %d", &x, &y) == 2);
P.push_back(Point(x, y));
}
Regions.push_back(P);
}
void Print() {
assert(freopen("regiuni.out", "w", stdout));
printf("%d\n", static_cast<int>(Regions.size()));
}
int main() {
Read();
Solve();
Print();
return 0;
}