Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1410 Intersection---计算几何

Posted on 2009-10-02 03:13 Uriel 阅读(378) 评论(0)  编辑 收藏 引用 所属分类: POJ计算几何
判断矩形与一线段是否相交,注意线段在矩形内部的情况
其他都是模板。。没什么了。。
/*Problem: 1410  User: Uriel 
   Memory: 172K  Time: 0MS 
   Language: C++  Result: Accepted
*/
 

#include
<stdio.h>
#include
<stdlib.h>
#include 
<math.h>
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)

struct point
{
    
double x,y;
}
;

struct line
{
    point a,b;
}
;

double xmult(point p1,point p2,point p0)
{
    
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}


int dot_online_in(point p,point l1,point l2)
{
    
return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
}


int dots_inline(point p1,point p2,point p3)
{
    
return zero(xmult(p1,p2,p3));
}


int same_side(point p1,point p2,point l1,point l2)
{
    
return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}


int intersect_in(point u1,point u2,point v1,point v2)
{
    
if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
    
{
        
return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
    }

    
return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);
}


point P1,P2,S1,S2,S3,S4;

int main()
{
    
int t,flag;
    
double temp;
    scanf(
"%d",&t);
    
while(t--)
    
{
        scanf(
"%lf %lf %lf %lf %lf %lf %lf %lf",&P1.x,&P1.y,&P2.x,&P2.y,&S1.x,&S1.y,&S2.x,&S2.y);
        
if(S1.x>S2.x)
        
{
            temp
=S1.x;
            S1.x
=S2.x;
            S2.x
=temp;
        }

        
if(S1.y<S2.y)
        
{
            temp
=S1.y;
            S1.y
=S2.y;
            S2.y
=temp;    
        }

        S3.x
=S1.x;
        S3.y
=S2.y;  
        S4.x
=S2.x;
        S4.y
=S1.y;
        flag
=0;
        
if(intersect_in(P1,P2,S1,S3) || intersect_in(P1,P2,S1,S4) || intersect_in(P1,P2,S2,S3) || intersect_in(P1,P2,S2,S4))
        
{
            flag
=1;
        }

        
if(P1.x>=S1.x && P1.x<=S2.x && P2.x>=S1.x && P2.x<=S2.x && P1.y<=S1.y && P1.y>=S2.y && P2.y<=S1.y && P2.y>=S2.y)
        
{
            flag
=1;
        }

        
if(!flag)
        
{
            printf(
"F\n");
        }

        
else
        
{
            printf(
"T\n");
        }

    }

//    system("PAUSE");
    return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理