Cod sursa(job #40902)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 27 martie 2007 20:31:06
Problema Regiuni Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <string.h>

#define MAXN 1024

int N, M;
short A[MAXN], B[MAXN], C[MAXN];

short x[MAXN], y[MAXN], s1[MAXN], s2[MAXN];

short gr[MAXN], grl[MAXN], grr[MAXN], nrgr;

inline int semn( short A, short B, short C, short x, short y )
{
	int D = ((int)A * x + (int)B * y + (int)C);

	if (D > 0) return 1;
	return 0;
}

int main()
{
	freopen("regiuni.in", "rt", stdin);
	freopen("regiuni.out", "wt", stdout);

	scanf("%d %d", &N, &M);

	int i, j;
	for (i = 0; i < N; i++)
		scanf("%hd %hd %hd", A + i, B + i, C + i);

	nrgr = 1; grl[0] = 0; grr[0] = M - 1;
	for (i = 0; i < M; i++)
	{
		scanf("%hd %hd", x + i, y + i);
		gr[i] = i;
	}

	for (i = 0; i < N; i++)
	{
		int _nrgr = nrgr;
		for (j = 0; j < _nrgr; j++)
		{
			int l = grl[j], r = grr[j], k;
			s1[0] = s2[0] = 0;

			for (k = l; k <= r; k++)
				if (semn( A[i], B[i], C[i], x[ gr[k] ], y[ gr[k] ] ))
					s1[++s1[0]] = gr[k];
				else
					s2[++s2[0]] = gr[k];

			if (!s1[0] || !s2[0])
				continue;

			grl[++nrgr] = l + s1[0];
			grr[nrgr] = grr[j];
			grr[j] = l + s1[0] - 1;

			for (k = 1; k <= s1[0]; k++)
				gr[k + grl[j] - 1] = s1[k];
			for (k = 1; k <= s2[0]; k++)
				gr[k + grl[nrgr] - 1] = s2[k];
		}
	}

	printf("%d\n", nrgr);
	return 0;
}