Cod sursa(job #614554)

Utilizator ChallengeMurtaza Alexandru Challenge Data 6 octombrie 2011 20:12:07
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="zoo.in";
const char OutFile[]="zoo.out";
const int MaxN=16111;
const int INF=2000111000;

ifstream fin(InFile);
ofstream fout(OutFile);

inline bool inter(const int &min1, const int &max1, const int &min2, const int &max2)
{
	if(max1<min2)
	{
		return false;
	}
	if(max2<min1)
	{
		return false;
	}
	return true;
}

struct aabb
{
	aabb(int xmin=0, int ymin=0, int xmax=0, int ymax=0):xmin(xmin),ymin(ymin),xmax(xmax),ymax(ymax){}
	int xmin,ymin,xmax,ymax;

	inline bool in(const aabb &a)
	{
		if(a.xmin<=xmin && xmax<=a.xmax && a.ymin<=ymin && ymax<=a.ymax)
		{
			return true;
		}
		return false;
	}
	inline bool inter(const aabb &a)
	{
		return ::inter(xmin,xmax,a.xmin,a.xmax) && ::inter(ymin,ymax,a.ymin,a.ymax);
	}
};

struct point
{
	point(int x=0, int y=0):x(x),y(y){}
	int x,y;

	inline bool in(const aabb &a)
	{
		if(a.xmin<=x && x<=a.xmax && a.ymin<=y && y<=a.ymax)
		{
			return true;
		}
		return false;
	}
};

struct point_cmp_x
{
	inline bool operator() (const point &a, const point &b)
	{
		return a.x<b.x;
	}
};

struct point_cmp_y
{
	inline bool operator() (const point &a, const point &b)
	{
		return a.y<b.y;
	}
};

struct kd_node
{
	kd_node *left,*right;
	point p;
	int count;
};

int N,M,sol;
point p[MaxN];
aabb q,space(INF,INF,-INF,-INF);
kd_node *root=NULL;

kd_node* kd_build(int st, int dr,bool vert=true)
{
	if(st>dr)
	{
		return NULL;
	}
	if(vert)
	{
		sort(p+st,p+dr+1,point_cmp_x());
	}
	else
	{
		sort(p+st,p+dr+1,point_cmp_y());
	}
	kd_node *ptr=new kd_node();
	int mid=st+((dr-st)>>1);
	ptr->p=p[mid];
	ptr->left=kd_build(st,mid-1,!vert);
	ptr->right=kd_build(mid+1,dr,!vert);
	ptr->count=dr-st+1;
	return ptr;
}

void kd_query(kd_node *node,aabb x,bool vert=true)
{
	if(!node)
	{
		return;
	}
	if(x.in(q))
	{
		sol+=node->count;
	}
	else
	{
		if(node->p.in(q))
		{
			++sol;
		}
		aabb left=x,right=x;
		if(vert)
		{
			left.xmax=node->p.x;
			right.xmin=node->p.x;
		}
		else
		{
			left.ymax=node->p.y;
			right.ymin=node->p.y;
		}
		if(q.inter(left))
		{
			kd_query(node->left,left,!vert);
		}
		if(q.inter(right))
		{
			kd_query(node->right,right,!vert);
		}
	}
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>p[i].x>>p[i].y;
		space.xmin=min(space.xmin,p[i].x);
		space.xmax=max(space.xmax,p[i].x);
		space.ymin=min(space.ymin,p[i].y);
		space.ymax=max(space.ymax,p[i].y);
	}
	fin>>M;

	root=kd_build(1,N);

	for(register int i=1;i<=M;++i)
	{
		sol=0;
		fin>>q.xmin>>q.ymin>>q.xmax>>q.ymax;
		kd_query(root,space);
		fout<<sol<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}