Cod sursa(job #37449)

Utilizator mastermageSchneider Stefan mastermage Data 25 martie 2007 09:46:51
Problema Regiuni Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.09 kb
#include <stdio.h>
#include <string.h>

#define maxN 1010

struct point{
	int x,y;
};

struct line{
	int a,b,c;
	int solve(const point&x)const{
		return a*x.x+b*x.y+c;
	}
	int dir(const point&x)const{
		if(a*x.x+b*x.y+c > 0)return 1; else return -1;
	}
};

int n,m,k=1, gr[maxN],asoc[maxN],ngr[maxN];
line vl[maxN]; point vp[maxN];

void inputFunc(){
	FILE*fi=fopen("regiuni.in","r");
	fscanf(fi,"%d %d",&n,&m);
	for(int i=0;i<n;i++)fscanf(fi,"%d %d %d",&vl[i].a,&vl[i].b,&vl[i].c);
	for(int i=0;i<m;i++)fscanf(fi,"%d %d",&vp[i].x,&vp[i].y);
	fclose(fi);
}

void outputFunc(){
	FILE*fi=fopen("regiuni.out","w");
	fprintf(fi,"%d",k);
	fclose(fi);
}

int main(){
	inputFunc();

	for(int i=0;i<n;i++){
		const line cl=vl[i];memset(asoc,0,sizeof*asoc*k);memset(ngr,-1,sizeof*ngr*k);
		
		for(int j=0;j<m;j++){
			const int r=cl.dir(vp[j]), cg=gr[j];
			if(!asoc[cg]){
				asoc[cg]=r;
			}else
			if(asoc[cg]!=r){
				if(ngr[cg]==-1){
					gr[j]=k;asoc[k]=r;ngr[cg]=k;
					++k;
				}else{
					gr[j]=ngr[cg];
				}
			}
		}
		
	}
	
	outputFunc();
	return 0;
}