Pagini recente » Cod sursa (job #578234) | Cod sursa (job #3187141) | Cod sursa (job #1710716) | Cod sursa (job #727494) | Cod sursa (job #1392065)
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
#define pb push_back
struct line{
int a, b, c;
};
struct point {
int x, y;
};
const int MAX_N = 1000 + 1;
const int MAX_M = 1000 + 1;
line l[MAX_N];
point p[MAX_M];
int n, m;
typedef vector<short int> group;
group v[MAX_N];
int lo, hi;
void showGroup(group A) {
for(int i = 0 ; i < (int)A.size() ; ++i) {
cout << A[i] << " ";
}
cout << "\n";
}
void showGroups() {
for(int i = lo ; i <= hi ; ++i)
showGroup(v[i]);
cout << "\n\n\n\n";
}
bool left(const point &P, const line &L) {
return (P.x * L.a + P.y * L.b + L.c) > 0;
}
group R;
bool bad[MAX_N];
void removeBad(group &v) {
int n = v.size() - 1;
for(int i = n ; i >= 0 ; --i) {
if(bad[i]) {
v[i] = v[n];
v.pop_back();
}
}
}
void consider(int w) {
for(int i = lo ; i <= hi ; ++i) {
group &now = v[i];
R.clear();
for(int i = 0 ; i < (int)now.size() ; ++i) {
const int pt = now[i];
bad[i] = 0;
if(!left(p[pt], l[w])) {
R.pb(pt);
bad[i] = 1;
}
}
removeBad(now);
if(now.empty())
swap(now, R);
if(!R.empty())
v[++hi] = R;
}
//showGroups();
}
int main() {
ifstream in("regiuni.in");
in >> n >> m;
for(int i = 1 ; i <= n ; ++i) {
in >> l[i].a >> l[i].b >> l[i].c;
}
group now;
for(int i = 1 ; i <= m ; ++i) {
in >> p[i].x >> p[i].y;
now.pb(i);
}
v[0] = now;
lo = hi = 0;
for(int i = 1 ; i <= n ; ++i)
consider(i);
ofstream out("regiuni.out");
out << (hi - lo + 1) << "\n";
out.close();
in.close();
return 0;
}