Cod sursa(job #37494)

Utilizator vlad_DVlad Dumitriu vlad_D Data 25 martie 2007 10:30:54
Problema Regiuni Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.72 kb
/*
Vlad Dumitriu
regiuni - infoarena
*/
#include <cstdio>

using namespace std;
int n, m;
int i, j, k;
struct ec {
	int A, B, C;
	ec(){};
	ec(int _a, int _b, int _c) {A = _a; B = _b; C = _c;};
	};
struct po {
	int X, Y;
	po(){};
	po(int _x, int _y) {X = _x; Y = _y;};
	};
ec E[1024];
po P[1024];
int R[1024][1024];
int K = 1;
int main() {
	freopen("regiuni.in", "r", stdin);
	freopen("regiuni.out", "w", stdout);
	scanf("%d %d", &m, &n);
	for (i=1; i<=m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		E[i] = ec(a, b, c);
	}
	for (i=1; i<=n; i++) {
		int a, b; scanf("%d %d", &a, &b);
		P[i] = po(a, b);
		}
	R[1][0] = n;
	for (i=1; i<=n; i++) R[1][i] = i;
	for (k=1; k<=m; k++) {
		double A = E[k].A, B = E[k].B, C = E[k].C;
		int K2 = K;
		for (int ok = 0, i=1; i<=K; i++) { 
			int MMM = 0;
			for (j=1; j<=R[i][0]; j++) {
				//r p
				// Ax By C
				double YY;
				if (B == 0.0) YY = -C/A;
					
				else
				YY =(-C - A*double(P[R[i][j]].X)) / B;
				if ((B!=0 &&YY >= double(P[R[i][j]].Y)) || (B == 0 && YY >= double(P[R[i][j]].X))) {
				/*	if (ok == 0) {ok = 1; K2++;}
						R[K2][R[K2][0]++] = R[i][j];
						R[i][j] = R[i][R[i][0]]; R[i][0]--;}*/
					MMM++;
				}}
			//printf("%dah\n", MMM);
			if (MMM != R[i][0]) 
				
				for (j=1; j<=R[i][0]; j++) {
				//r p
				// Ax By C
				double YY;
				if (B == 0) YY = -C/A;
					
				else
				YY =(-C - A*double(P[R[i][j]].X)) / B;
				if ((B!=0 &&YY >= double(P[R[i][j]].Y)) || (B == 0 && YY >= double(P[R[i][j]].X))) {
					if (ok == 0) {ok = 1; K2++;}
						R[K2][R[K2][0]++] = R[i][j];
						R[i][j] = R[i][R[i][0]]; R[i][0]--;}
					//MMM++;
				}

				
		}
		K = K2;		
		}
	printf("%d\n", K);
	return 0;
}