#include<stdio.h>

int main()
{
	
}

bool squareCrossAndInCheck(int xs1[4],int ys1[4],int xs2[4],int ys[4]){
	bool tb1,tb2,isInSquare=true;
	for(int i=0;i<4;i++){
		//四角形の中に四角形があるのかのチェック
		//片方の四角形を三角形に分割して行う
		tb1=inTriangle(xs1[0],xs1[1],xs1[2],xs2[i],ys1[0],ys1[1],ys1[2],ys2[i]);
		tb2=inTriangle(xs1[2],xs1[3],xs1[0],xs2[i],ys1[2],ys1[3],ys1[0],ys2[i]);
		if(tb1==false && tb2==false) isInSquare=false;
	}
	if(isInSquare==true) return true;
	bool isUnionSquare=false;
	//四角形の線分同士が共有部分を持つかを調べる
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(cross(xs1[i],xs1[(i+1)%4],xs2[i],xs2[(i+1)%4],ys1[i],ys1[(i+1)%4],ys2[i],ys2[(i+1)%4])==true){
				isUnionSquare=true;
				break;
			}
		}
		if(isUnionSquare==true) break;
	}
	return isUnionSquare;
	
}

bool inTriangle(int x1,int x2,int x3,int x4,int y1,int y2,int y3,int y4){
	//四角形を分割した三角形の中に点があるか
	//これは四角形の中に四角形がある場合を判別するために使用される
	//分割した三角形を表す点(x1,y1)(x2,y2)(x3,y3) と点(x4,y4)が三角形の中にあるかをチェックする関数
	//三角形は辺上も含む
	//三角形の線分を伸ばし直線とし平面を切り分けた時、三角形の残りの点と(x4,y4)が同じ半開平面になければfalseを変えす
	//共通集合として三角形を定義している
	int t1,t2;
	t1=lineHerf(x1,x2,x3,y1,y2,y3);
	t2=lineHerf(x1,x2,x4,y1,y2,y4);
	if(t1*t2<0) return false;
	t1=lineHerf(x1,x3,x2,y1,y3,y2);
	t2=lineHerf(x1,x3,x4,y1,y3,y4);
	if(t1*t2<0) return false;
	t1=lineHerf(x2,x3,x1,y2,y3,y1);
	t2=lineHerf(x2,x3,x4,y2,y3,y4);
	if(t1*t2<0) return false;
	return true;
}


bool cross(int x1,int x2,int x3,int x4,int y1,int y2,int y3,int y4){
	//２つの四角形を構成する線分が点、辺上に点もしくは交点を持つかどうかのチェックに使う
	//共有部分を持つならtrueを持たないならfalseを返す
	//線分(x1,y1)(x2,y2)と線分(x3,y3)(x4,y4)の共通部分を調べる
	int t1,t2,t3,t4;
	//点を共有してないか
	if(x1==x3 && y1==y3) return true;
	if(x1==x4 && y1==y4) return true;
	if(x2==x3 && y2==y3) return true;
	if(x2==x4 && y2==y4) return true;
	
	//線分が交点を持つか
	t1=lineHerf(x1,x2,x3,y1,y2,y3);
	t2=lineHerf(x1,x2,x4,y1,y2,y4);
	if(t1*t2>0) return false;
	t3=lineHerf(x3,x4,x1,y3,y4,y1);
	t4=lineHerf(x3,x4,x2,y3,y4,y2);
	if(t3*t4>0) return false;
	//両方の線分が交点を持つ
	if(t1*t2<0 && t3*t4<0) return true;
	//片方の点がもう片方の線分の上にある
	if((t1*t2==0 && t3*t4<0) || (t1*t2<0 && t3*t4==0)) return true;
	if(t1*t2==0 && t3*t4==0){
		//両片が平行な場合
		//線分上のある点からみて両側に片方の線分の点があるか
		t1=pointHerf(x1,x2,x3,y1,y2,y3);
		t2=pointHerf(x1,x2,x4,y1,y2,y4);
		if(t1*t2<0) return true;
		t1=pointHerf(x2,x1,x3,y2,y1,y3);
		t2=pointHerf(x2,x1,x4,y2,y1,y4);
		if(t1*t2<0) return true;
		t1=pointHerf(x3,x4,x1,y3,y4,y1);
		t2=pointHerf(x3,x4,x2,y3,y4,y2);
		if(t1*t2<0) return true;
		t1=pointHerf(x4,x3,x1,y4,y3,y1);
		t2=pointHerf(x4,x3,x2,y4,y3,y2);
		if(t1*t2<0) return true;
	}
	//点を共有せず、交点も持たず、片方の線分上に片方の線分がないかつ線分が平行で重なることもない場合
	return false;
}
int pointHerf(int x1,int x2,int x3,int y1,int y2,int y3){
	//２つの線分が並行で同一直線状にある時、線分の点のどちら側にもう片方の線分の点があるかをチェックする関数
	return (x2-x1)*(x3-x1)+(y2-y1)*(y3-y1);
}

int lineHerf(int x1,int x2,int x3,int y1,int y2,int y3){
	//直線で切り分けた時の半開平面のどちら側に点があるか
	return (y2-y1)*(x3-x1)+y1*(x2-x1)+(x1-x2)*y3;
}