Cod sursa(job #39273)

Utilizator TYTUSVlad Saveluc TYTUS Data 26 martie 2007 16:24:43
Problema Regiuni Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <vector>
using namespace std;

typedef pair<int, int>point;

int a[1000], b[1000], c[1000];
vector<vector<point> >v;

int main() {
	FILE *fin = fopen ("regiuni.in", "r");
	FILE *fout = fopen ("regiuni.out", "w");
	int n, m, i;
	fscanf (fin, "%d %d", &n, &m);
	for (i = 0; i < n; ++i) {
		fscanf (fin, "%d %d %d", &a[i], &b[i], &c[i]);
	}
	v.push_back(vector<point>());
	for (i = 0; i < m; ++i) {
		int x, y;
		fscanf (fin, "%d %d", &x, &y);
		v[0].push_back(make_pair(x, y));
	}
	for (i = 0; i < n; ++i) {
		int j, s = v.size();
		for (j = 0; j < s; ++j) {
			vector<point>minus, plus;
			vector<point>::iterator it;
			for (it = v[j].begin(); it != v[j].end(); ++it) {
				if (it->first * a[i] + it->second * b[i] + c[i] < 0) {
					minus.push_back(*it);
				} else {
					plus.push_back(*it);
				}
			}
			if (minus.size() > 0 && plus.size() > 0) {
				v[j] = minus;
				v.push_back(plus);
			}
		}
	}
	fprintf (fout, "%d\n", v.size());
	fclose(fout);
	return 0;
}