Pagini recente » Cod sursa (job #1080728) | Cod sursa (job #76410) | Cod sursa (job #2209785) | Cod sursa (job #1704354) | Cod sursa (job #285559)
Cod sursa(job #285559)
#include <stdio.h>
#define MAX_N 1024
struct punct {
int x;
int y;
} v[MAX_N];
struct drepte {
int a;
int b;
int c;
} dr[MAX_N];
int i, j, k, n, m, sol, x, nr, nxt;
int point[MAX_N], aux[2][MAX_N], start[MAX_N], stop[MAX_N];
void cit() {
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; i++)
scanf("%d %d", &v[i].x, &v[i].y);
}
void solve() {
start[1] = 1; stop[1] = m; sol = 1;
for (i = 1; i <= m; i++) point[i] = i;
for (i = 1; i <= n; i++) {
nr = sol;
//vad cum va desparti dreapta i regiunile deja formate
for (j = 1; j <= m;) {
aux[0][0] = aux[1][0] = 0;
for (k = start[j]; k <= stop[j]; k++)
if (dr[i].a * v[point[k]].x + dr[i].b * v[point[k]].y + dr[i].c < 0)
aux[0][++aux[0][0]] = point[k];
else
aux[1][++aux[1][0]] = point[k];
//formez doua noua grupe
x = j; nxt = stop[j] + 1;
if (aux[0][0] && aux[1][0]) {
stop[x] = x + aux[0][0] - 1;
for (k = 1; k <= aux[0][0]; k++)
point[x++] = aux[0][k];
start[x] = x;
stop[x] = x + aux[1][0] - 1;
for (k = 1; k <= aux[1][0]; k++)
point[x++] = aux[1][k];
nr++;
}
j = nxt;
}
sol = nr;
}
printf("%d\n", sol);
}
int main() {
cit();
solve();
return 0;
}