Pagini recente » Cod sursa (job #833788) | Cod sursa (job #2985889) | Cod sursa (job #2091409) | Cod sursa (job #3196385) | Cod sursa (job #286080)
Cod sursa(job #286080)
#include <cstdio>
const int MAX_N = 1000;
int n, m, z1, z2, sol;
int reg1[MAX_N], reg2[MAX_N], r[MAX_N];
struct punct {
int x, y;
} p[MAX_N];
struct dreapta {
int a, b, c;
} d[MAX_N];
struct regiune {
int s, f;
} reg[MAX_N];
int main()
{
int i, j, k;
freopen("regiuni.in", "r", stdin);
freopen("regiuni.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 1; i <= n; ++i) scanf("%d %d %d", &d[i].a, &d[i].b, &d[i].c);
for (i = 1; i <= m; r[i] = i, ++i) scanf("%d %d", &p[i].x, &p[i].y);
reg[1].s = 1, reg[1].f = m, sol = 1;
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= m;)
{
z1 = z2 = 0;
for (k = reg[j].s; k <= reg[j].f; ++k)
if (d[i].a * p[r[k]].x + d[i].b * p[r[k]].y + d[i].c > 0) reg1[++z1] = r[k];
else reg2[++z2] = r[k];
int q = reg[j].f + 1;
if (z1 && z2)
{
reg[j].f = j + z1 - 1;
for (k = 1; k <= z1; ++k) r[++j] = reg1[k];
reg[j].s = j;
reg[j].f = j + z1 - 1;
for (k = 1; k <= z2; ++k) r[++j] = reg2[k];
++sol;
}
j = q;
}
}
printf("%d\n", sol);
}