Pagini recente » Cod sursa (job #2166381) | Cod sursa (job #186284) | Cod sursa (job #400513) | Cod sursa (job #2489981) | Cod sursa (job #37600)
Cod sursa(job #37600)
#include <fstream>
#define MAX 1001
using namespace std;
int n, m;
int g[MAX], h[MAX];
bool u[MAX];
struct dreapta{
int a, b, c;
} d[MAX];
struct punct{
int x, y;
} p[MAX];
int Check(int x1, int y1);
void Union(int x, int y);
int Find(int x);
int main()
{
int i, j, nr = 0, ok, x;
ifstream fin("regiuni.in");
fin >> m >> n;
for (i = 1; i <= m; i++)
fin >> d[i].a >> d[i].b >> d[i].c;
for (i = 1; i <= n; i++)
{
fin >> p[i].x >> p[i].y;
g[i] = i;
h[i] = 0;
}
fin.close();
for (i = 1; i <= n; i++)
{
ok = 1;
memset(u, 0, sizeof(u));
for (j = 1; j <= n && ok; j++)
if (i != j)
{
x = Find(j);
if (u[x]) continue;
if (Check(i, x))
{
ok = 0;
Union(i, x);
}
else u[x] = 1;
}
}
ofstream fout("regiuni.out");
memset(u, 0, sizeof(u));
for (i = 1; i <= n; i++)
{
x = Find(i);
if (!u[x])
{
u[x] = 1;
nr++;
}
}
fout << nr << "\n";
fout.close();
}
int Check(int x1, int y1)
{
int i, aux1, aux2;
for (i = 1; i <= m; i++)
{
aux1 = d[i].a*p[x1].x + d[i].b*p[x1].y + d[i].c;
aux2 = d[i].a*p[y1].x + d[i].b*p[y1].y + d[i].c;
if ((aux1 > 0 && aux2 < 0) || (aux1 < 0 && aux2 > 0)) return 0;
}
return 1;
}
void Union(int x, int y)
{
x = Find(x);
if (x == y) return;
if (h[x] > h[y]) g[y] = x;
else
{
g[x] = y;
if (h[x] == h[y]) ++h[y];
}
}
int Find(int x)
{
if ( x != g[x] ) g[x] = Find(g[x]);
return g[x];
}