Cod sursa(job #25323)

Utilizator crusRus Cristian crus Data 4 martie 2007 11:59:22
Problema Ograzi Scor 30
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.38 kb
#include <stdio.h>
#define nmax 100001
#define input "ograzi.in"
#define output "ograzi.out"
long n,m,h,w,sol=0,j,l1,l2,x0,y0;
long s1[nmax],s2[nmax],s3[nmax],s4[nmax],x[nmax],y[nmax],i;
void merge(int ls, int ld)
{
	if (ls<ld)
		{
		 long i,j,k=(ls+ld)/2;
		 merge(ls,k);
		 merge(k+1,ld);
		 long l1=0;
		 long l2=0;
		 for (i=ls;i<=k;i++)
			{
			 s1[++l1]=x[i];
			 s2[l1]=y[i];
			}
		 for (i=k+1;i<=ld;i++)
			{
			 s3[++l2]=x[i];
			 s4[l2]=y[i];
			}
		 i=1;
		 j=1;
		 k=ls-1;
		 while (i<=l1&&j<=l2)
			{
			 if ((s1[i]<s3[j])||(s1[i]==s3[j]&&s2[i]<=s4[j]))
				{
				 k++;
				 x[k]=s1[i]; 
				 y[k]=s2[i];
				 i++;
				}
			 else
				{
				 k++;
				 x[k]=s3[j];
				 y[k]=s4[j];
				 j++;
				}
			}
		 while (i<=l1)
			{
			 k++;
			 x[k]=s1[i];
			 y[k]=s2[i];
			 i++;
			}
		 while (j<=l2)
			{
			 k++;
			 x[k]=s3[j];
			 y[k]=s4[j];
			 j++;
			}
		}
}
int main()
{
	FILE *fin,*fout;
	fin=fopen(input,"r");
	fout=fopen(output,"w");
	fscanf(fin,"%ld %ld %ld %ld",&n,&m,&w,&h);
	for (i=1;i<=n;i++)
		fscanf(fin,"%ld %ld",&x[i],&y[i]);
	merge(1,n);
    for (i=1;i<=m;i++)
		{
		 fscanf(fin,"%ld %ld",&x0,&y0);		 
		 for (j=1;j<=n;j++)
			 if ((x0>=x[j]&&x0-x[j]<=w)&&(y0>=y[j]&&y0-y[j]<=h)) {sol++; break;}
			 else
			 if (x[j]>x0) break;
		}
	fclose(fin);
	fprintf(fout,"%ld",sol);
	fclose(fout);
	return 0;
}