Pagini recente » Cod sursa (job #2513425) | Cod sursa (job #766557) | Cod sursa (job #2030080) | Cod sursa (job #2278620) | Cod sursa (job #48347)
Cod sursa(job #48347)
#include <stdio.h>
#define NMAX 1001
int n, m, x[2][NMAX], dr[NMAX], ns, nd;
typedef struct
{int a, b, c;}DREPTE;
DREPTE d[NMAX];
typedef struct
{int x, y;}PUNCTE;
PUNCTE y[2][NMAX], p[NMAX];
void read()
{
int i, j;
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 (j = 1; j <= m; j++)
scanf("%d%d", &p[j].x, &p[j].y), x[0][j] = j;
}
int semn(int i, int j)
{
int r;
r = d[i].a*p[j].x+d[i].b*p[j].y+d[i].c;
if (r>0)
return 1;
else
return 0;
}
void adauga(int i, int dr[], int nd)
{
int j, beg, k;
if (nd != 0)
{
k = i&1;
beg = y[k][x[k][0]].y+1;
x[k][0]++;
y[k][x[k][0]].x = beg;
for (j = 1; j <= nd; j++, beg++)
x[k][beg] = dr[j];
y[k][x[k][0]].y = beg-1;
}
}
void rezolv()
{
int i, j, lim, k, beg, ci, p, q;
x[0][0] = 1;
y[0][1].x = 1;
y[0][1].y = m;
for (i = 1; i <= n; i++)
{
x[i&1][0]=0;
ci = (i-1)&1;
lim = x[ci][0];
p=i&1;
for (j = 1; j <= lim; j++)
{
beg=y[p][x[p][0]].y;
for (k = y[ci][j].x; k <= y[ci][j].y; k++)
{
if (semn(i,x[ci][k]))
dr[++nd] = x[ci][k];
else
x[p][++beg] = x[ci][k], ns++;
}
if (ns!=0)
{
x[p][0]++;
q = y[p][x[p][0]-1].y+1;
y[p][x[p][0]].x = q;
y[p][x[p][0]].y = q+ns-1;
}
adauga(i, dr, nd);
nd = ns =0;
}
}
printf("%d\n", x[(i-1)&1][0]);
}
int main()
{
freopen("regiuni.in", "r", stdin);
freopen("regiuni.out", "w", stdout);
read();
rezolv();
return 0;
}