Cod sursa(job #45261)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 1 aprilie 2007 12:24:13
Problema Regiuni Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <list>
#include <utility>
using namespace std;

#define FIN "regiuni.in"
#define FOUT "regiuni.out"
#define MAX 1000
#define f first
#define s second
#define pb push_back
#define pf push_front
#define FOR(i,x,y) for(i=x;i<y;++i)
#define mp make_pair


typedef pair<long,long> punct;
typedef list< punct > vector;
list <vector> Gr;
vector aux;
long A[MAX][3];
long n,m;

inline int dr(long i, long x, long y) {
//	return 0;
	return (A[i][0]*x+A[i][1]*y+A[i][2] <= 0) ? 0 : 1;
}

void debug(vector x) {
	vector::iterator i;
	for (i=x.begin(); i!=x.end(); ++i)
		printf("Aux are pe (%ld %ld)!\n", i->f, i->s);
}

int main() {
	long i,x,y, ok;
	list<vector>::iterator j, pj;
	vector::iterator k,p;

	freopen(FIN, "r", stdin);
	scanf("%ld %ld", &n, &m);
	FOR (i,0,n)
		scanf("%ld %ld %ld", A[i], A[i]+1, A[i]+2);
	FOR (i,0,m) {
		scanf("%ld %ld", &x, &y);
		aux.pb(mp(x,y));
	}
	fclose(stdin);

	Gr.pb( aux );
	FOR (i,0,n) {
		for (j=Gr.begin(); j!=Gr.end(); ) {
			aux.clear();
			for (k=j->begin(); k!=j->end(); ) {
				ok = 1;
//				fprintf(stderr, "Prelucrat punctul (%ld %ld)!\n", k->f, k->s);
				if ( dr(i, k->f, k->s)>0 ) {
					aux.pb(mp(k->f, k->s));
					p = k; k--;
					j->erase(p);
					k++;
					ok = 0;
				}
				if ( ok ) 
					k++;
			}
//			debug(aux);
			if ( !aux.empty() )
				Gr.pf(aux);
			if ( j->empty() ) {
				pj = j; j--;
				Gr.erase(pj);
				j++;
			}
			else 
				j++;
		}
	}

	freopen(FOUT, "w", stdout);
	printf("%ld\n", Gr.size());
	fclose(stdout);
}