poj1410巧妙變成直線與線段相交

  這題粗看還以為是線段與線段相交，但是題目要求，線段完全在矩形內也是算相交。所以可以變成目標線段a所在的直線與矩形的各個線段相交問題，然後再看該線段a是否在矩形范圍內。

[cpp] 
#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; 
}