460

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstdio>

using namespace std;

struct point{
	int x,y;
};
point LL1,LL2,LR1,LR2,UL1,UL2,UR1,UR2;
point New_LL,New_LR,New_UL,New_UR;

bool isOverlap()
{
	if(LL1.x>=LR2.x)
	return 0;
	if(LR1.x<=LL2.x)
	return 0;

	if(LL1.y>=UL2.y)
	return 0;
	if(UL1.y<=LL2.y)
	return 0;
	return 1;
}

bool isTotalInside()
{
	if((LL1.x>=LL2.x && LL1.x <= UR2.x) && (LL1.y>=LL2.y && LL1.y <= UR2.y))
	{
		if((LR1.x>=LL2.x && LR1.x <= UR2.x) && (LR1.y>=LL2.y && LR1.y <= UR2.y))
		{
			if((UR1.x>=LL2.x && UR1.x <= UR2.x) && (UR1.y>=LL2.y && UR1.y <= UR2.y))
			{
				if((UL1.x>=LL2.x && UL1.x <= UR2.x) && (UL1.y>=LL2.y && UL1.y <= UR2.y))
				{
					New_LL.x=LL1.x;
					New_LL.y=LL1.y;

					New_UR.x=UR1.x;
					New_UR.y=UR1.y;
					return 1;
				}
			}
		}
	}
	if((LL2.x>=LL1.x && LL2.x <= UR1.x) && (LL2.y>=LL1.y && LL2.y <= UR1.y))
	{
		if((LR2.x>=LL1.x && LR2.x <= UR1.x) && (LR2.y>=LL1.y && LR2.y <= UR1.y))
		{
			if((UR2.x>=LL1.x && UR2.x <= UR1.x) && (UR2.y>=LL1.y && UR2.y <= UR1.y))
			{
				if((UL2.x>=LL1.x && UL2.x <= UR1.x) && (UL2.y>=LL1.y && UL2.y <= UR1.y))
				{
					New_LL.x=LL2.x;
					New_LL.y=LL2.y;

					New_UR.x=UR2.x;
					New_UR.y=UR2.y;
					return 1;
				}
			}
		}
	}
	return 0;

}
int InsidePoints()
{
	if(isTotalInside())
	return 0;
	if(LL1.x>=LL2.x && LL1.x <= UR2.x)
	{
		if(LL1.y>=LL2.y && LL1.y <= UR2.y)
		{
			//vb.push_back(LL1);
			New_LL.x=LL1.x;
			New_LL.y=LL1.y;

			New_LR.x= (LR2.x<=LR1.x?LR2.x:LR1.x);
			New_LR.y= New_LL.y;

			New_UL.x=New_LL.x;
			New_UL.y=(UL2.y<=UL1.y?UL2.y:UL1.y);

			New_UR.x=New_LR.x;
			New_UR.y=New_UL.y;
			return 0;
		}

		New_LL.x=LL1.x;
		New_LL.y=LL2.y;

		New_UR.x=(LR1.x<=LR2.x?LR1.x:LR2.x);
		New_UR.y=(UR1.y<=UR2.y?UR1.y:UR2.y);
		return 0;
	}
	if(LR1.x>=LL2.x && LR1.x <= UR2.x)
	{
		if(LR1.y>=LL2.y && LR1.y <= UR2.y)
		{
			//vb.push_back(LL1);
			New_LR.x=LR1.x;
			New_LR.y=LR1.y;

			New_LL.x= (LL2.x<=LL1.x?LL1.x:LL2.x);
			New_LL.y= New_LR.y;

			New_UL.x=New_LL.x;
			New_UL.y=(UL2.y<=UL1.y?UL2.y:UL1.y);

			New_UR.x=New_LR.x;
			New_UR.y=New_UL.y;
			return 0;
		}
		New_LL.x=LL2.x;
		New_LL.y=LL2.y;

		New_UR.x=LR1.x;
		New_UR.y=(UR1.y<=UR2.y?UR1.y:UR2.y);
		return 0;
	}

	if(UR1.x>=LL2.x && UR1.x <= UR2.x)
	{
		if(UR1.y>=LL2.y && UR1.y <= UR2.y)
		{
			//vb.push_back(LL1);
			New_UR.x=UR1.x;
			New_UR.y=UR1.y;

			New_UL.x=(UL1.x<=UL2.x?UL2.x:UL1.x);
			New_UL.y=New_UR.y;

			New_LL.x= New_UL.x;
			New_LL.y= (LL1.y<=LL2.y?LL2.y:LL1.y);

			New_LR.x=New_UR.x;
			New_LR.y=New_LL.y;
			return 0;
		}
		New_UR.x=UR1.x;
		New_UR.y=(UR1.y<=UR2.y?UR1.y:UR2.y);

		New_LL.x=(LL1.x>=LL2.x?LL1.x:LL2.x);
		New_LL.y=(LL1.y>=LL2.y?LL1.y:LL2.y);
		return 0;
	}

	if(UL1.x>=LL2.x && UL1.x <= UR2.x)
	{
		if(UL1.y>=LL2.y && UL1.y <= UR2.y)
		{
			//vb.push_back(LL1);
			New_UL.x=UL1.x;
			New_UL.y=UL1.y;

			New_UR.x=(UR1.x<=UR2.x?UR1.x:UR2.x);
			New_UR.y=New_UL.y;

			New_LL.x= New_UL.x;
			New_LL.y= (LL1.y<=LL2.y?LL2.y:LL1.y);

			New_LR.x=New_UR.x;
			New_LR.y=New_LL.y;
			return 0;
		}
		New_LL.x=UL1.x;
		New_LL.y=(LL1.y>=LL2.y?LL1.y:LL2.y);

		New_UR.x=(UR1.x<=UR2.x?UR1.x:UR2.x);
		New_UR.y=(UR1.y<=UR2.y?UR2.y:UR1.y);
		return 0;
	}
	return -1;
}
int main()
{
	int t;
	int length1,length2,width1,width2;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d%d",&LL1.x,&LL1.y,&UR1.x,&UR1.y);
		scanf("%d%d%d%d",&LL2.x,&LL2.y,&UR2.x,&UR2.y);

		length1 = abs(LL1.x - UR1.x);
		width1 = abs(LL1.y - UR1.y);
		length2 = abs(LL2.x - UR2.x);
		width2 = abs(LL2.y - UR2.y);

		LR1.x = UR1.x; 	LR1.y = LL1.y;
		UL1.x = LL1.x;	UL1.y = UR1.y;
		LR2.x = UR2.x;	LR2.y = LL2.y;
		UL2.x = LL2.x;	UL2.y = UR2.y;

		if(!isOverlap())
		{
			printf("No Overlap\n");
			if(t)
			printf("\n");
			continue;
		}
		if(InsidePoints()==0)
		printf("%d %d %d %d\n",New_LL.x,New_LL.y,New_UR.x,New_UR.y);
		if(t)
			printf("\n");
	}
	return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *