2473.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Memory:64K  Time:250MS
Language:C++  Result:Accepted

Source 

#include"iostream.h"
#include"algorithm"

struct rect
{
	int x1,x2,y1,y2;
}r[210];

int n,w,h,n1,n2,m;
int x[411],y[411];

void init()
{
	int i;
	cin>>n>>w>>h;
	for(i=0;i<n;i++)
	{
		cin>>r[i].x1>>r[i].y1>>r[i].x2>>r[i].y2;
		x[i]=r[i].x2;
		y[i]=r[i].y2;
	}

	m=n+1;
	x[n]=0,y[n]=0;

	std::sort(x,x+m);
	std::sort(y,y+m);
	n1=std::unique_copy(x,x+m,x)-x;
	n2=std::unique_copy(y,y+m,y)-y;
}

inline int max(int a,int b)
{
	return a>b?a:b;
}
inline int min(int a,int b)
{
	return a<b?a:b;
}

void doit()
{
	int ww,hh,i,j,k=0;
	
	cin>>ww>>hh;
	
	for(i=0;i<n1;i++)
	if(y[i]+hh<=h)
		for(j=0;j<n2;j++)
		{
			if(x[j]+ww<=w)
			{
				for(k=0;k<n;k++)
				if(min(r[k].x2,x[j]+ww)>max(r[k].x1,x[j])&&min(r[k].y2,y[i]+hh)>max(r[k].y1,y[i]))
					break;
				if(k==n)
					goto loop;
			}
		}
loop:
	if(i<n1)
		cout<<x[j]<<' '<<y[i]<<endl;
	else cout<<"Fail!"<<endl;
}

int main()
{
	int cas;
	cin>>cas;
	while(cas--)
	{
		init();
		doit();
	}
	return 0;
}