Cod sursa(job #40064)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 27 martie 2007 11:01:07
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
# include <stdio.h>
# include <string.h>
# include <math.h>

# define  _fin	"regiuni.in"
# define  _fout "regiuni.out"

# define  maxn	1001


int x[maxn], y[maxn], 					// puncte
	a[maxn], b[maxn], c[maxn],			// linii
	m, n, i, j, k, ok, sol;
short *g[maxn], ng,
	g1[maxn], g2[maxn];


inline int sign(int x) { return x>0?1:-1; }
inline int calc(int i, int j) { return a[i]*x[j]+b[i]*y[j]+c[i]; };

void readf()
{
	freopen(_fin, "r", stdin);
	for (scanf("%d%d", &m, &n), i=1; i<=m; i++) scanf("%d%d%d", a+i, b+i, c+i);
	for (i=1; i<=n; i++) scanf("%d%d", x+i, y+i);
}

void solve()
{
//	int aux;
	g[1]=new short[4*maxn];
	for (i=ng=1, g[1][0]=n; i<=n; i++) g[1][i]=i;
	
	for (i=1; i<=m; i++) {
		for (j=ng; j>=1; j--)
		{
			g1[0]=g2[0]=0;
			for (k=1; k<=g[j][0]; k++)
				if ( sign( calc(i, g[j][k]) )>0 ) g1[++g1[0]] = g[j][k];
				else g2[++g2[0]] = g[j][k];
			
			if ( g1[0]&&g2[0] ) {
				memcpy(g[j], g1, sizeof(short)*(g1[0]+1));
				g[++ng] = g[j]+g1[0]+1;
				memcpy(g[ng], g2, sizeof(short)*(g2[0]+1));
//				delete g[j];
//				g[j] = new short[ g1[0]+1 ];
//				g[++ng] = new short[ g2[0]+1 ];
//				memcpy(g[j], g1, sizeof(short)*(g1[0]+1));
//				memcpy(g[ng], g2, sizeof(short)*(g2[0]+1));
			}
		}
	}
}

int main()
{
	readf();
	freopen(_fout,"w", stdout);
	solve();
	printf("%d\n", ng);
	
	return 0;
}