poj1410巧妙变成直线与线段相交

这题粗看还以为是线段与线段相交，但是题目要求，线段完全在矩形内也是算相交。所以可以变成目标线段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;elsereturn 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;}