Cod sursa(job #37522)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 25 martie 2007 10:43:20
Problema Regiuni Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 0.95 kb
#include <cstdio>
#define FIN "regiuni.in"
#define FOUT "regiuni.out"
#define MAX 1024
#define FOR(l,h,i) for(i=l;i<h;++i)

struct punct {
	long x, y;
} P[MAX];
struct dreapta {
	long a,b,c;
} D[MAX];

long a[MAX],b[MAX], max, N,M;

inline int loc(dreapta D, punct B) {
	return (D.a*B.x + D.b*B.y + D.c) < 0 ? 0 : 1;
}
bool g[MAX*MAX][2];
long g2[MAX*MAX];

int main() {
	long i, j;

	freopen(FIN, "r", stdin);
	scanf("%ld %ld", &N, &M);
	FOR(0,N,i)
		scanf("%ld %ld %ld", &D[i].a, &D[i].b, &D[i].c);
	FOR(0,M,i)
		scanf("%ld %ld", &P[i].x, &P[i].y);
	fclose(stdin);

	FOR (0,M,i)
		b[i] = 1;
	max = 1;
	FOR (0,N,i) {
		FOR (0,max,j)
			g[j][0] = g[j][1] = false;
		FOR (0,M,j) {
			g[ b[j] ] [ a[j] = loc(D[i], P[j]) ] = true;
		}
		long nr=max;
		FOR (1,nr+1,j)
			if ( g[j][0] && g[j][1] ) {
				g2[j] = ++max;
			}
		FOR (0,N,j)
			if ( a[j] && g[j][0] && g[j][1] ) 
				b[j] = g2[j];
	}

	freopen(FOUT, "w", stdout);
	printf("%ld\n", max);
	fclose(stdout);
	return 0;
}