Cod sursa(job #38998)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 26 martie 2007 12:39:01
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <stdio.h>
#define fin  "regiuni.in"
#define fout "regiuni.out"
#define Nmax 1001

struct dot {
	int x;
	int y;
	int comp;
};

struct ec {
	int a;
	int b;
	int c;
};

int K,N,M,use[Nmax],reg1[Nmax],reg2[Nmax];
dot pct[Nmax];
ec  line[Nmax];

int main() {
int i,j,k;
double xct,yct,side;
	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%i%i",&N,&M);

	for (i=1;i<=N;++i) 
		scanf("%i%i%i",&line[i].a,&line[i].b,&line[i].c);

	for (i=1;i<=M;++i) {
		scanf("%i%i",&pct[i].x,&pct[i].y);
		pct[i].comp=1;
	}

	K=1;

	for (i=1;i<=N;++i) {

		for (j=1;j<=M;++j) {
			use[j]=0;
			reg1[j]=0;
			reg2[j]=0;
		}

		if (line[i].a==0 && line[i].b==0) ;

		else

		if (line[i].a==0) {
			yct=-(double)line[i].c/(double)line[i].b;
			for (j=1;j<=M;++j) {
				side=yct-pct[j].y;
				if (side<0) 
					reg1[pct[j].comp]++;
				else
					reg2[pct[j].comp]++;
			}

			for (j=1;j<=M;++j)
				if (reg1[j] && reg2[j]) { 
					++K;
					use[j]=K;
				}
			for (j=1;j<=M;++j) {
				side=yct-pct[j].y;
				if (side<0 && use[pct[j].comp]) 
					pct[j].comp=use[pct[j].comp];
				
			}


		}
		else

		if (line[i].b==0) {
			xct=-(double)line[i].c/(double)line[i].a;
			//printf("%lf\n",xct);
			for (j=1;j<=M;++j) {
				side=xct-pct[j].x;
				if (side<0) 
					reg1[pct[j].comp]++;
					
				else 
					reg2[pct[j].comp]++;
			}
			for (j=1;j<=M;++j)
				if (reg1[j] && reg2[j]) { 
					++K;
					use[j]=K;
				}
			for (j=1;j<=M;++j) {
				side=xct-pct[j].x;
				if (side<0 && use[pct[j].comp]) 
					pct[j].comp=use[pct[j].comp];
				
			}


		}

		else {
			for (j=1;j<=M;++j) {
				yct=(double)(-line[i].c-line[i].a*pct[j].x)/(double)line[i].b;
				side=yct-pct[j].y;
				if (side<0) 
					reg1[pct[j].comp]++;
					
				else 
					reg2[pct[j].comp]++;
			}
			
			for (j=1;j<=M;++j)
				
				if (reg1[j] && reg2[j]) { 
					++K;
					use[j]=K;
				}

			for (j=1;j<=M;++j) {
				yct=(double)(-line[i].c-line[i].a*pct[j].x)/(double)line[i].b;
				side=yct-pct[j].y;
				if (side<0 && use[pct[j].comp]) 
					pct[j].comp=use[pct[j].comp];
				}
		}			
		
	}

	printf("%i\n",K);

	fclose(stdin); fclose(stdout);

	return 0;

}