Cod sursa(job #40120)

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

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

# define  maxn	1001

typedef struct grp
{
	int x;
	grp *next;
}	*pgrp;

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

pgrp g[maxn], g1, g2, r, q;

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;
	for (i=ng=1; i<=n; i++)	r=new grp, r->x=i, r->next=g[1], g[1]=r;
	
	for (i=1; i<=m; i++)
		for (j=ng; j>=1; j--) {
			g1=g2=NULL;
			for (r=g[j]; r; )
				if ( sign(calc(i, r->x)) > 0 ) {
					q=r, r=r->next;
					q->next=g1, g1=q;
				}
				else {
					q=r, r=r->next;
					q->next=g2, g2=q;
				}
			if ( g1!=NULL && g2!=NULL ) {
				g[++ng]=g2, g[j]=g1;
			}
			else if ( g1 ) g[j]=g1;
			else if ( g2 ) g[j]=g2;
		}
/*		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(int)*(g1[0]+1));
				g[++ng] = g[j]+g1[0]+1;
//				memcpy(g[ng], g2, sizeof(int)*(g2[0]+1));
				for (k=1,g[j][0]=g1[0]; k<=g1[0]; k++) g[j][k]=g1[k];
				for (k=1,g[ng][0]=g2[0]; k<=g2[0];k++) g[ng][k]=g2[k];
//				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;
}