Pagini recente » Monitorul de evaluare | Cod sursa (job #133514) | Cod sursa (job #1253387) | Cod sursa (job #2598052) | Cod sursa (job #1891645)
#include <fstream>
#include <vector>
#include <list>
using namespace std;
ifstream fin ("regiuni.in");
ofstream fout ("regiuni.out");
class dreapta { public : int a, b, c; } N[1010];
class punct { public : int x, y; } M[1010];
int n, m, g = 1;
vector < int > Plus, Minus;
list < int > L[10010];
int Pos(punct p, dreapta d)
{
return (d.a * p.x + d.b * p.y + d.c);
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= n; i ++)
{
fin >> N[i].a >> N[i].b >> N[i].c;
}
for (int i = 1; i <= m; i ++)
{
fin >> M[i].x >> M[i].y;
L[g].push_back(i);
}
for (int i = 1; i <= n; i ++)
{
for (int j = 1, jj = g; j <= jj; j ++)
{
while (!Plus.empty()) Plus.pop_back();
while (!Minus.empty()) Minus.pop_back();
for (list < int > :: iterator it = L[j].begin(); it != L[j].end(); it ++)
{
if (Pos(M[*it], N[i]) > 0) Plus.push_back(*it);
else Minus.push_back(*it);
}
if (Plus.size() && Minus.size())
{
g ++;
if (Plus.size() < Minus.size())
{
for (list < int > :: iterator it = L[j].end(); it != L[j].begin(); it --)
{
if (*it == Plus.back())
{
L[j].erase(it);
L[g].push_back(Plus.back());
Plus.pop_back();
if (Plus.empty()) break;
}
}
}
else
{
for (list < int > :: iterator it = L[j].end(); it != L[j].begin(); it --)
{
if (*it == Minus.back())
{
L[j].erase(it);
L[g].push_back(Minus.back());
Minus.pop_back();
if (Minus.empty()) break;
}
}
}
}
}
}
fout << g << '\n';
fout.close();
return 0;
}