Pagini recente » Cod sursa (job #3371) | Cod sursa (job #1401692) | Cod sursa (job #2420320) | Cod sursa (job #2332015) | Cod sursa (job #40224)
Cod sursa(job #40224)
#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 )
{
int i;
for (i = 0; i <= N >> 3; i++)
if (smn[a][i] != smn[b][i])
return smn[a][i] < smn[b][i];
return 0;
}
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++] = o[i++];
else
tmp[k++] = o[j++];
for (k = l; k <= r; k++) o[k] = tmp[k];
}
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);
for (i = 0; i < M; i++)
{
int X, Y;
scanf("%d %d", &X, &Y);
for (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 (i = 1; i < M; i++)
{
int ok = 1;
for (j = 0; ok && j <= N >> 3; j++)
ok = (smn[i][j] == smn[i - 1][j]);
nM += !ok;
}
printf("%u\n", nM);
return 0;
}