Pagini recente » Rezultatele filtrării | Borderou de evaluare (job #17070) | Rezultatele filtrării | Cod sursa (job #1891709)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("regiuni.in");
ofstream out("regiuni.out");
const int MAXN = 1005;
struct punct
{
int x,y;
bool operator != (punct &b)
{
return this -> x != b.x || this -> y != b.y;
}
};
struct dreapta
{
int a,b,c;
int parte(punct p)
{
long long nr = (long long)a * p.x + (long long)b * p.y + c;
if (nr < 0)
return -1;
return 1;
}
};
int n,m;
dreapta drepte[MAXN];
vector<vector<punct>*> grupe;
void citire()
{
in >> n >> m;
for (int i = 1;i <= n;++i)
in >> drepte[i].a >> drepte[i].b >> drepte[i].c;
grupe.push_back(new vector<punct>);
grupe[0]->reserve(m);
for (int i = 1;i <= m;++i)
{
int x,y;
in >> x >> y;
grupe[0]->push_back((punct){x,y});
}
}
void prelucrare()
{
vector<punct>* grupa_supl = NULL;
for (int dr = 1;dr <= n;++dr)
{
unsigned int lim = grupe.size();
for (unsigned int i = 0;i < lim;++i)
//separare grupa in doua in functie de partea pe care punctele sunt pe dreapta
{
int parte = drepte[dr].parte((*grupe[i])[0]);
if (grupa_supl == NULL)
grupa_supl = new vector<punct>;
for (unsigned int j = 1;j < grupe[i]->size();++j)
{
punct p = (*grupe[i])[j];
if (drepte[dr].parte(p) != parte)
grupa_supl->push_back(p);
}
if (grupa_supl->size() > 0)
{
unsigned int cursorsupl = 0,cursorj = 1;
for (unsigned int j = 1;j < grupe[i]->size();++j)
if ((*grupe[i])[j] != (*grupa_supl)[cursorsupl])
{
(*grupe[i])[cursorj] = (*grupe[i])[j];
++cursorj;
}
else ++cursorsupl;
grupe[i]->resize(cursorj);
grupe.push_back(grupa_supl);
grupa_supl = NULL;
}
}
/*for (unsigned int i = 0;i < grupe.size();++i)
{
if (grupe[i]->size() == 0)
{
delete grupe[i];
grupe[i] = NULL;
}
}
unsigned int cursor = 0;
for (unsigned int i = 0;i < grupe.size();++i)
{
if (grupe[i] != NULL)
{
grupe[cursor] = grupe[i];
++cursor;
}
}
grupe.resize(cursor);*/
}
}
int main()
{
citire();
prelucrare();
out << grupe.size() << '\n';
return 0;
}