Cod sursa(job #277871)

Utilizator MarquiseMarquise Marquise Data 11 martie 2009 22:48:20
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>

#define NMAX 1005


int N, M, r, x[NMAX][NMAX], R, pd[NMAX], ps[NMAX];


struct POINT
{
	int x, y;
};
POINT p[NMAX];


struct DREAPTA
{
	int a, b, c;
};
DREAPTA d[NMAX];


void rezolv()
{
	int i, j, k;

	r = 1;
	x[r][0] = M;

	for ( i = 1; i <= M; i++)
		x[r][i] = i;


	for ( i = 1; i <= N; i++)
	{


		R = r;

		for ( j = 1; j <= r; j++)
		{

			pd[0] = ps[0] = 0;

			for (k = 1; k <= x[j][0]; k++)
				if ( p[x[j][k]].x * d[i].a + p[x[j][k]].y * d[i].b + d[i].c > 0)
					pd[++pd[0]] = x[j][k];
				else
					ps[++ps[0]] = x[j][k];


		   if ( pd[0] )
		   {
				for ( k = 0; k <= pd[0]; k++)
					x[j][k] = pd[k];

				if ( ps[0])
				{
					R++;
					for ( k = 0; k <= ps[0]; k++)
						x[R][k] = ps[k];
				}
		   }
		   else
		   {
				for ( k = 0; k <= ps[0]; k++)
					x[j][k] = ps[k];
		   }

		}

		r = R;
	}


	printf("%d\n", r);
}



int main()
{
	int i;

	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; i++)
		scanf("%d %d", &p[i].x, &p[i].y);

	rezolv();

	return 0;
}