Cod sursa(job #37509)

Utilizator plastikDan George Filimon plastik Data 25 martie 2007 10:40:51
Problema Regiuni Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.11 kb
#include <cstdio>
#include <cstdlib>

#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 1024;
int N, M;
struct vertex {
	int x, y;
} V[MAX_N];
struct line {
	int a, b, c;
} L[MAX_N];
int whatnext[MAX_N];

vector<int> tag;

inline int Line(int i, int j) { // verifica pe ce parte a dreptei i se afla punctul j
	return L[i].a * V[j].x + L[i].b * V[j].y + L[i].c;
}

int main(void) {
	FILE *in = fopen("regiuni.in", "r");
	fscanf(in, "%d %d", &N, &M);
	int i;
	for (i = 0; i < N; ++ i) {
		fscanf(in, "%d %d %d", &L[i].a, &L[i].b, &L[i].c);
	}
	
	tag.reserve(M);
	for (i = 0; i < M; ++ i) {
		tag.push_back(1);
		fscanf(in, "%d %d", &V[i].x, &V[i].y);
	}
	fclose(in);
	
	int j, max;
	whatnext[1] = 2;
	for (i = 0; i < N; ++ i) {
		max = 0;
		for (j = 0; j < M; ++ j) {
			if (Line(i, j) > 0) {
				tag[j] = whatnext[tag[j]];
				if (max < tag[j])
					max = tag[j];
			}
		}
		for (j = 1; j <= max; ++ j)
			whatnext[j] = max + j;		
	}

	vector<int>::iterator end = unique(tag.begin(), tag.end());
	FILE *out = fopen("regiuni.out", "w");
	fprintf(out, "%d\n", end - tag.begin());
	fclose(out);	


	return 0;
}