Pagini recente » Cod sursa (job #429702) | Cod sursa (job #3211299) | Cod sursa (job #382320) | Cod sursa (job #863503) | Cod sursa (job #1392011)
#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#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<int> group;
deque<group> v;
void showGroup(group A) {
for(int i = 0 ; i < (int)A.size() ; ++i) {
cout << A[i] << " ";
}
cout << "\n";
}
void showGroups() {
for(int i = 0 ; i < (int)v.size() ; ++i)
showGroup(v[i]);
cout << "\n\n\n\n";
}
bool cross(const point &P, const line &L) {
double xp1 = 0,
yp1 = - 1.0 * L.c / L.b;
double xp2 = - 1.0 * L.c / L.a,
yp2 = 0;
double x1 = xp2 - xp1,
y1 = yp2 - yp1;
double x2 = P.x - xp2,
y2 = P.y - yp2;
return (x1 * y2 - x2 * y1) < 0;
}
bool left(const point &P, const line &L) {
if(L.b == 0) {
return P.x < (-1.0 * L.c / L.a);
} else if(L.a == 0) {
return P.y > (-1.0 * L.c / L.b);
} else {
return cross(P, L);
}
}
void consider(int w) {
group L, R;
for(int i = 0 ; i < (int)v.size() ; ++i) {
const group &now = v.front();
L.clear();
R.clear();
for(int i = 0 ; i < (int)now.size() ; ++i) {
const int pt = now[i];
if(left(p[pt], l[w]))
L.pb(pt);
else
R.pb(pt);
}
v.pop_front();
if(!L.empty())
v.pb(L);
if(!R.empty())
v.pb(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.pb(now);
for(int i = 1 ; i <= n ; ++i)
consider(i);
ofstream out("regiuni.out");
out << v.size() << "\n";
out.close();
in.close();
return 0;
}