Cod sursa(job #37628)

Utilizator crusRus Cristian crus Data 25 martie 2007 11:32:05
Problema Regiuni Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 1.54 kb
#include <stdio.h>
#include <string.h>
#define input "regiuni.in"
#define output "regiuni.out"
#define nmax 1001
int n,m,i,nr1,nr2,cnt1,cnt2,t,k;
int a[nmax],b[nmax],c[nmax],x[nmax],y[nmax],s1[nmax],s2[nmax],f1[nmax],f2[nmax],a1[nmax],a2[nmax],y1[nmax],x1[nmax];
void citire()
{
	FILE *fin;
	fin=fopen(input,"r");
	fscanf(fin,"%d %d",&n,&m);
	for (i=1;i<=n;i++)
		fscanf(fin,"%d %d %d",&a[i],&b[i],&c[i]);
	for (i=1;i<=m;i++)
		fscanf(fin,"%d %d",&x[i],&y[i]);
	fclose(fin);
}
void copiaza()
{
 if (nr1)
	{
	 cnt2++;
	 s2[cnt2]=s1[t];
	 f2[cnt2]=s1[t]+nr1-1;
	 memcpy(x1,x,sizeof(x1));
	 memcpy(y1,y,sizeof(y1));
	 for (i=1;i<=nr1;i++)
		{	
		 x[s2[cnt2]+i-1]=x1[a1[i]];
		 y[s2[cnt2]+i-1]=y1[a1[i]];
		}
	}
 if (nr2)
	{
	 cnt2++;
	 s2[cnt2]=s1[t]+nr1;
	 f2[cnt2]=f1[t];
	 memcpy(x1,x,sizeof(x1));
	 memcpy(y1,y,sizeof(y1));
	 for (i=1;i<=nr2;i++)
		{	
		 x[s2[cnt2]+i-1]=x1[a2[i]];
		 y[s2[cnt2]+i-1]=y1[a2[i]];
		}
	}
}
void determina()
{
 for (i=s1[t];i<=f1[t];i++)
	if (a[k]*x[i]+b[k]*y[i]+c[k]>0)
		{
		 nr1++;
		 a1[nr1]=i;	
		}
	else
		{
		 nr2++;
		 a2[nr2]=i;
		}
}
void solve()
{
	cnt1=1;
	s1[1]=1;
	f1[1]=m;
	for (k=1;k<=n;k++)
		{
		 cnt2=0;
		 for (t=1;t<=cnt1;t++)
			{
		 	 nr1=0;
			 nr2=0;
			 determina();
			 copiaza();
			}	
		 cnt1=cnt2;
		 memcpy(s1,s2,sizeof(s1));
		 memcpy(f1,f2,sizeof(f1));
		}
}
void afisare()
{
	FILE *fout;
	fout=fopen(output,"w");
	fprintf(fout,"%d",cnt1);
	fclose(fout);
}
int main()
{
	citire();
	solve();
	afisare();
	return 0;
}