poj 1410は線分と直線に巧みに交差する

この問題はざっと見ると線分と線分が交差していると思っていたが,線分は完全に矩形内でも交差していることが要求された.したがって、ターゲット線分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
");
					HaveInteraction=true;
				}
				break;
			}
		}

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

	return 0;
}