Cod sursa(job #25798)

Utilizator megabyteBarsan Paul megabyte Data 4 martie 2007 14:43:55
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <cstdio>
#include <iterator>
#include <list>
#define SEGT 2000002
#define NMAX 50002
#define MMAX 100002
#define INF "ograzi.in"
#define OUF "ograzi.out"
using namespace std;
struct cord
{
	int x,y;
}pt[NMAX],sheep[MMAX];
int seg[SEGT]={0},a,b;
void qsort_byx(cord *a,int li,int ls)
{
	int i,j,piv;
	cord aux;
	i=li;j=ls;piv=a[i].x;
	do
	{
		while(a[i].x<piv) i++;
		while(a[j].x>piv) j--;
		if(i<=j)
		{
			aux=a[i];a[i]=a[j];a[j]=aux;
			i++;j--;
		}
	}while(i<j);
	if(i<ls) qsort_byx(a,i,ls);
	if(j>li) qsort_byx(a,li,j);
}
void insert(int nod,int li,int ls)
{
    if(a<=li&&ls<=b) seg[nod]++;
    else
    {
	    int mij;
	    mij=(li+ls)/2;
	    if(a<=mij) insert(2*nod,li,mij);
	    if(b>mij) insert(2*nod+1,mij+1,ls);
	    seg[nod]++;
    }
}
void extract(int nod,int li,int ls)
{
	if(a<=li&&ls<=b) seg[nod]--;
	else
	{
		int mij;
		mij=(li+ls)/2;
		if(a<=mij) extract(2*nod,li,mij);
		if(b>mij) extract(2*nod+1,mij+1,ls);
		seg[nod]--;
	}
}
int query(int nod,int li,int ls)
{
	if(a<=li&&ls<=b) return seg[nod];
	else
	{
		int mij,rez=0;
		mij=(li+ls)/2;
		if(a<=mij) rez+=query(2*nod,li,mij);
		if(b>mij) rez+=query(2*nod+1,mij+1,ls);
		return rez;
	}
}
int main()
{
	FILE *in,*out;
	int i,j,hi,n,m,w,h,total=0,ymax=0;
	list<int> lt;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%d %d %d %d",&n,&m,&w,&h);
	for(i=1;i<=n;i++) fscanf(in,"%d %d",&pt[i].x,&pt[i].y);
	for(i=1;i<=m;i++)
	{
		fscanf(in,"%d %d",&sheep[i].x,&sheep[i].y);
		if(ymax<sheep[i].y+1) ymax=sheep[i].y+1;
	}
	qsort_byx(pt,1,n);
	qsort_byx(sheep,1,m);
	j=1;
	while(sheep[j].x<pt[1].x)
	{
		j++;
	}
	for(i=1;i<n;i++)
	{
		hi=pt[i].x+w;
		while(j<=m&&sheep[j].x<=hi) 
		{
			a=b=sheep[j].y+1;insert(1,1,ymax);
			lt.push_back(j);
			j++;
		}
		a=pt[i].y+1;b=pt[i].y+h+1;
		total+=query(1,1,ymax);//printf("%d\n",total);
		while(!lt.empty()&&sheep[*lt.begin()].x<pt[i+1].x) { a=b=sheep[*lt.begin()].y+1; extract(1,1,ymax); lt.pop_front();}
	}
	//printf("%d\n%d\n",hi,sheep[j].x);
	//for(i=1;i<2*ymax;i++) printf("%d ",seg[i]);
	//printf("%d %d\n",lo,j);
	hi=pt[i].x+w;
	while(j<=m&&sheep[j].x<=hi) 
	{
		a=b=sheep[j].y+1;insert(1,1,ymax);
		j++;
	}
	a=pt[i].y+1;b=pt[i].y+h+1;
	total+=query(1,1,ymax);
	fprintf(out,"%d",total);
	fclose(in);fclose(out);
	return 0;
}