Pagini recente » Cod sursa (job #2186492) | Cod sursa (job #3183491) | Cod sursa (job #184639) | Cod sursa (job #1982647) | Cod sursa (job #286083)
Cod sursa(job #286083)
#include <cstdio>
const int MAX_N = 1010;
struct punct {
int x, y;
} p[MAX_N];
struct dreapta {
int a, b, c;
} dr[MAX_N];
struct regiune {
int s, f;
} reg[MAX_N];
int i, j, k, n, m, sol, x, nr, nxt, z1, z2;
int r[MAX_N], regiune[2][MAX_N];
int main()
{
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", &dr[i].a, &dr[i].b, &dr[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 (dr[i].a * p[r[k]].x + dr[i].b * p[r[k]].y + dr[i].c < 0) regiune[0][++z1] = r[k];
else regiune[1][++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++] = regiune[0][k];
reg[j].s = j;
reg[j].f = j + z2 - 1;
for (k = 1; k <= z2; k++) r[j++] = regiune[1][k];
++sol;
}
j = q;
}
}
printf("%d\n", sol);
}