Cod sursa(job #40170)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 27 martie 2007 11:46:53
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <string.h>

#define MAXN 1024

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

short o[MAXN], tmp[MAXN];
unsigned char smn[MAXN][MAXN >> 3];

inline void set1( int x, int y ) { smn[x][y >> 3] |= (1 << (y & 7)); }

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

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

inline int less( short a, short b )
{
	for (int i = 0; i <= N >> 3; i++)
		if (smn[a][i] != smn[b][i])
			return smn[a][i] < smn[b][i];
	return 0;
}

inline int eq( short a, short b )
{
	for (int i = 0; i <= N >> 3; i++)
		if (smn[a][i] != smn[b][i])
			return 0;
	return 1;
}

int qsortcmp( const void *a, const void *b )
{
	if ( less( *(int *)a, *(int *)b ) )
		return -1;
	if ( eq( *(int *)a, *(int *)b ) )
		return 0;
	return 1;
}

inline void sort( int l, int r )
{
	if (l == r)
		return;
	
	int m = (l + r) >> 1, i, j, k;
	sort(l, m);
	sort(m + 1, r);

	for (i = k = l, j = m + 1; i <= m || j <= r; )
		if (j > r || (i <= m && less( o[i], o[j] )))
			tmp[k++] = i++;
		else
			tmp[k++] = j++;
	memcpy(o, tmp, sizeof(o));
}

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

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

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

	for (int i = 0; i < M; i++)
	{
		int X, Y;
		scanf("%d %d", &X, &Y);

		for (int j = 0; j < N; j++)
			if ( semn( A[j], B[j], C[j], X, Y ) )
				set1( i, j );
		o[i] = i;
	}

	sort(0, M - 1);

	int nM = 1;
	for (int i = 1; i < M; i++)
		if (!eq( o[i], o[i - 1] ))
			nM++;
	printf("%u\n", nM);
	return 0;
}