频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj1410巧妙变成直线与线段相交
2012-08-01 09:37:19           
收藏   我要投稿

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

点击复制链接 与好友分享!回本站首页
相关TAG标签 线段 直线
上一篇:poj_3264 Balanced Lineup
下一篇:poj2418二叉查找树
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站