设为首页 加入收藏

TOP

HDU 1086 You can Solve a Geometry Problem too(判断线段相交）
2015-07-20 17:54:59 来源: 作者: 【大 中 小】 浏览:2次
Tags：HDU 1086 You can Solve Geometry Problem too 判断 线段 相交

题目地址：HDU 1086

就这么一道仅仅判断线段相交的题目写了2k多B的代码。。是不是有点浪费。。。但是我觉得似乎哪里也优化不了了。。。。

判断线段相交就是利用的叉积。假如现在两条线段分别是L1和L2，先求L1和L2两个端点与L1的某个端点的向量的叉积，如果这两个的叉积的乘积小于0的话，说明L1在是在L2两个端点之间的，但此时并不保证一定相交。此时需要用同样的方法去判断L2是否在L1的两个端点之间，如果L2也在L1的两个端点之间的话，那就足以说明L1与L2相交。但是这题还需要判断是否端点也相交，当时没想到这点，导致白白调了一段时间。。至于端点的判断，我也没想到什么好的方法。。就直接暴力判断4个端点是否是同一点的情况。。

搓代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define eqs 1e-10 struct node { double x, y; } point[1000]; node xiang(node a, node b) { node f1; f1.x=a.x-b.x; f1.y=a.y-b.y; return f1; } int cross(node a, node b) { double c; c= a.x*b.y-a.y*b.x; if(c>0) return 1; else if(c==0) return 0; else return -1; } int dcmp(double x, double y) { if(fabs(x-y)<=eqs) return 1; return 0; } int main() { int n, i, j; int c1, c2, c3, c4, ans; while(scanf("%d",&n)!=EOF&&n) { ans=0; for(i=0; i
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：C++构造函数 & 拷贝构造函数 & 派.. 下一篇：poj3322 Bloxorz I

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: