Cod sursa(job #48347)

Utilizator ZuziFilip Sanziana Zuzi Data 4 aprilie 2007 18:16:18
Problema Regiuni Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#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;
}