Cod sursa(job #277852)

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

#define NMAX 1005

int N, M, r, x[NMAX][NMAX], y[NMAX][NMAX];


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


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


void rezolv()
{
	int i, j, k, num = 0;

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

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


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

		for ( j = 1; j < num; j++)
			y[j][0] = 0;

		num = 1;

		for ( j = 1; j <= r; j++, num += 2)
		{

			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)
					y[num][++y[num][0]] = x[j][k];
				else
					y[num + 1][++y[num + 1][0]] = x[j][k];
		}

		r = 0;
		for ( j = 1; j < num; j++)
			if ( y[j][0] )
			{
				r++;
				for ( k = 0; k <= y[j][0]; k++)
					x[r][k] =  y[j][k];
			}
	}


	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;
}