学步园

  这题粗看还以为是线段与线段相交，但是题目要求，线段完全在矩形内也是算相交。所以可以变成目标线段a所在的直线与矩形的各个线段相交问题，然后再看该线段a是否在矩形范围内。

#include <iostream>
using namespace std;


struct Point
{
	Point()
	{
		x=0.0f;
		y=0.0f;
	}

	Point(double tx,double ty)
	{
		x=tx;
		y=ty;
	}

	double x,y;
};

struct Segment
{
	Point point1,point2;
};

double Min(double a,double b)
{
	if(a<b)
		return a;
	else 
		return b;
}

double Max(double a,double b)
{
	if(a<b)
		return b;
	else 
		return a;
}

double CrossProduct(Point vec1,Point vec2)
{
	return (vec1.x*vec2.y)-(vec1.y*vec2.x);
}

//Calculate the crossproduct of (p2-p1)*(p3-p1)
double Direction(Point point1,Point point2,Point point3)
{
	Point vec1;
	vec1.x=point2.x-point1.x;
	vec1.y=point2.y-point1.y;

	Point vec2;
	vec2.x=point3.x-point1.x;
	vec2.y=point3.y-point1.y;

	return CrossProduct(vec1,vec2);
}

//See if line interact the segment.
bool LineInteractSegment(Segment line,Segment seg)
{
	Point vec1;
	vec1.x=line.point2.x-line.point1.x;
	vec1.y=line.point2.y-line.point2.y;

	Point vec2;
	vec2.x=seg.point2.x-seg.point1.x;
	vec2.y=seg.point2.y-seg.point2.y;

	double cross1=CrossProduct(
		 Point(line.point2.x-line.point1.x,line.point2.y-line.point1.y ),
		 Point(seg.point1.x-line.point1.x,seg.point1.y-line.point1.y));

	double cross2=CrossProduct(
		 Point(line.point2.x-line.point1.x,line.point2.y-line.point1.y ),
		 Point(seg.point2.x-line.point1.x,seg.point2.y-line.point1.y));

	if(cross1*cross2<=0)
		return true;
	else
		return false;
}

bool SegmentInRect(Segment seg,Point leftTopPoint,Point rightBottomPoint )
{
	double minX=Min(seg.point1.x,seg.point2.x);
	double maxX=Max(seg.point1.x,seg.point2.x);

	double minY=Min(seg.point1.y,seg.point2.y);
	double maxY=Max(seg.point1.y,seg.point2.y);

	if(minX>rightBottomPoint.x || maxX<leftTopPoint.x)
	{
		return false;
	}
	else
	{
		if(minY>leftTopPoint.y || maxY<rightBottomPoint.y)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
}

void SwapData(double& a,double& b)
{
	double c=a;
	a=b;
	b=c;
	return;
}

int main()
{
	bool HaveInteraction=false;
	Segment seg;
	Segment rectSeg[4];
	double leftTopX,leftTopY,rightBottomX,rightBottomY;

	int tCase;
	//cin>>tCase;
	scanf("%d",&tCase);
	while(tCase>0)
	{
		tCase--;

		//cin>>seg.point1.x>>seg.point1.y>>seg.point2.x>>seg.point2.y;
		scanf("%lf%lf%lf%lf",&seg.point1.x,&seg.point1.y,&seg.point2.x,&seg.point2.y);

		//cin>>leftTopX>>leftTopY>>rightBottomX>>rightBottomY;
		scanf("%lf%lf%lf%lf",&leftTopX,&leftTopY,&rightBottomX,&rightBottomY);

		if(leftTopX>rightBottomX)
			SwapData(leftTopX,rightBottomX);
		if(rightBottomY>leftTopY)
			SwapData(rightBottomY,leftTopY);

		//start from | ,take turn in clockwise.
		rectSeg[0].point1= Point(leftTopX,rightBottomY);
		rectSeg[0].point2= Point(leftTopX,leftTopY);

		rectSeg[1].point1= Point(leftTopX,leftTopY);
		rectSeg[1].point2= Point(rightBottomX,leftTopY);

		rectSeg[2].point1= Point(rightBottomX,leftTopY);
		rectSeg[2].point2= Point(rightBottomX,rightBottomY);

		rectSeg[3].point1= Point(rightBottomX,rightBottomY);
		rectSeg[3].point2= Point(leftTopX,rightBottomY);

		HaveInteraction=false;
		for(int i=0;i<4;i++)
		{
			if(LineInteractSegment(seg,rectSeg[i]))//the line interact with the rectangle, see if the segment interact the rectangle too.
			{
				if(SegmentInRect(seg, Point(leftTopX,leftTopY), Point(rightBottomX,rightBottomY)))
				{
					//cout<<"T"<<endl;
					printf("T\n");
					HaveInteraction=true;
				}
				break;
			}
		}

		if(HaveInteraction==false)
		{
			//cout<<"F"<<endl;
			printf("F\n");
		}
		
	}

	return 0;
}