Cod sursa(job #21742)

Utilizator mastermageSchneider Stefan mastermage Data 24 februarie 2007 10:59:17
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <string.h>

#define maxN 1010
#define maxM 1010
#define maxL 2010

char c;
int n,m,l,gr[maxN],viz[maxN],alone[maxN];


struct equ{
	int a,b,c;
	int res(int x,int y){
		return a*x+b*y+c;
	}
};
equ lines[maxM];

struct point{
	int x,y;
};
point drui[maxN];

int main(){
	FILE*fi=fopen("druid.in","r"),*fo=fopen("druid.out","w");
	while(1){
		fscanf(fi,"%d %d %d ",&n,&m,&l);
		for(int i=0;i<n;i++){
			fscanf(fi,"%d %d ",&drui[i].x,&drui[i].y);
		}
		for(int i=0;i<m;i++){
			fscanf(fi,"%d %d %d ",&lines[i].a,&lines[i].b,&lines[i].c);
		}
		
		int k=1;
		for(int i=0;i<n;i++)gr[i]=0,alone[i]=0;
		alone[0]=n;
		
		for(int i=0;i<m;i++){
			memset(viz,0,n*sizeof(*viz));equ ce=lines[i];
			for(int j=0;j<n;j++)if(!viz[j] && alone[gr[j]]>1 ){
				int cg=gr[j],log=0,cc=ce.res(drui[j].x,drui[j].y);
				for(int u=j+1;u<n;u++)if(gr[u]==cg){
					viz[u]=1;
					int d=ce.res(drui[u].x,drui[u].y);
					if((d<0) ^ (cc<0))gr[u]=k,log++;
				}
				
				if(log)alone[k]=log,alone[cg]-=log,k++;
			}
		}
		
		int log=1;
		for(int i=0;i<n;i++){
			if(alone[gr[i]]>1){
				fprintf(fo,"YES\n");log=0;break;
			}
		}
		if(log)fprintf(fo,"NO\n");
		
		if(feof(fi))break;fscanf(fi," %c ",&c);
	}
	
	fclose(fi);fclose(fo);
	return 0;
}