比赛 20120722 评测结果 AWWWWWWWTT
题目名称 切割矩形 最终得分 10
用户昵称 Citron酱 运行时间 2.003 s
代码语言 C++ 内存使用 1.32 MiB
提交时间 2012-07-22 13:03:04
显示代码纯文本
#include <cstdio>
#include <cstdlib>

#define I_F "cutting.in"
#define O_F "cutting.out"

const int MAXn=30000;
const int MAXq=30000;
const short P=20;

struct lib
{
	long x1,x2,y1,y2;
	lib *prep,*succ;
};
struct line
{
	long x1,x2,y;
};

lib pool[MAXn];
lib *ph, *s;
line p[MAXq];
long ans;
int n,q;

template<typename Any>
inline void Swap(Any&, Any&);
void Input();
void Sort(const int&, const int&);
void Search();
void Output();

int main()
{
	freopen(I_F,"r",stdin);
	freopen(O_F,"w",stdout);
	short t;
	for (scanf("%hd",&t); t>0; --t)
	{
		Input();
		Sort(0,q-1);
		Search();
		Output();
	}
	return 0;
}

template<typename Any>
inline void Swap(Any &a, Any &b)
{
	Any t=a;
	a=b;
	b=t;
}

void Input()
{
	ph=pool;
	s=NULL;
	lib *temp;
	scanf("%d",&n);
	for (int i=0; i<n; ++i)
	{
		temp=s;
		s=ph++;
		s->succ=temp;
		s->prep=NULL;
		if (temp!=NULL)
			temp->prep=s;
		scanf("%ld%ld%ld%ld",&s->x1,&s->y1,&s->x2,&s->y2);
	}
	scanf("%d",&q);
	for (int i=0; i<q; ++i)
		scanf("%ld%ld%ld%*d",&p[i].x1,&p[i].y,&p[i].x2);
}

void Sort(const int &l, const int &r)
{
	if (r-l>P)
	{
		long x=p[l+rand()%(r-l+1)].y;
		int i=l, j=r;
		do
		{
			while (p[i].y<x) ++i;
			while (p[j].y>x) --j;
			if (i<=j)
				Swap(p[i++],p[j--]);
		} while (i<j);
		if (i<r) Sort(i,r);
		if (l<j) Sort(l,j);
	}
	else
	{
		bool flag=true;
		for (int i=l; i<r && flag; ++i)
		{
			flag=false;
			for (int j=r; j>i; --j)
				if (p[j-1].y>p[j].y)
					Swap(p[j-1],p[j]),
					flag=true;
		}
	}
}

void Search()
{
	ans=0;
	for (int i=0; i<q; ++i)
		for (lib *j=s; j!=NULL; j=j->succ)
			if (j->y2<p[i].y)
			{
				if (j->succ!=NULL)
					j->succ->prep=j->prep;
				if (j->prep!=NULL)
					j->prep->succ=j->succ;
				else
					s=j->succ;
			}
			else
				if (((j->y1==p[i].y || j->y2==p[i].y) && j->x1<=p[i].x2 && j->x2>=p[i].x1) ||
					((j->y1<p[i].y && j->y2>p[i].y) && ((p[i].x1<=j->x1 && p[i].x2>=j->x1) || 
														(p[i].x1<=j->x2 && p[i].x2>=j->x2))))
					++ans;
}

void Output()
{
	printf("%ld\n",ans);
}