付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0

这是hdu 上面的入门几何题  判断线段相交 ,在算法导论上有相应的算法
而且这道题 没有考虑多条线段相交一点的情况
http://acm.hdu.edu.cn/showproblem.php?pid=1086

#include <stdio.h>
struct point
{
    
double x;
    
double y;
};
typedef 
struct point Point;
struct line
{
    Point s;
    Point e;
};
typedef 
struct line Line;
Line data[
110];
double min(double x,double y)
{
    
return x>? y:x;
}
double max(double x,double y)
{
    
return x<? y:x;
}
bool iszero(double f)
{
    
if (f < 0.00001 && f > -0.00001)
        
return true;
    
return false;
}
double direction(Point pi,Point pj,Point pk )
{
    
double x1,x2,y1,y2;
    x1 
= pk.x - pi.x;y1=pk.y-pi.y;
    x2 
= pj.x - pi.x;y2=pj.y-pi.y;
    
return x1*y2-x2*y1;
}
bool onsegment(Point pi,Point pj,Point pk ) //我换一种表示
{
    
if(( min(pi.x,pj.x) <= pk.x && pk.x <= max(pi.x,pj.x)) && ( min(pi.y,pj.y) <= pk.y && pk.y <= max(pi.y,pj.y) ))
      
//if( (pk.x-pi.x)*(pk.x-pj.x) <=0 && (pk.y-pi.y)*(pk.y-pj.y)<=0 ) //这也是判断点在pi pj 为对角线的矩形内
        return true;
    
return false;
}
bool SEGMENTS_INTERSECT(Point p1,Point p2,Point p3,Point p4)
{
    
double d1,d2,d3,d4;
    d1 
= direction(p3,p4,p1);
    d2 
= direction(p3,p4,p2);
    d3 
= direction(p1,p2,p3);
    d4 
= direction(p1,p2,p4);

    
if((d1*d2 < 0&&( d3*d4<0))
        
return true;
    
else if( iszero(d1) && onsegment(p3,p4,p1) ) return true;
    
else if( iszero(d2) && onsegment(p3,p4,p2) ) return true;
    
else if( iszero(d3) && onsegment(p1,p2,p3) ) return true;
    
else if( iszero(d4) && onsegment(p1,p2,p4) ) return true;
    
else return false;
}

int main(int argc, char* argv[])
{
    
int n,i,j,count;
    
while(scanf("%d",&n),n)
    {
        
for(i = 1; i <= n; i ++)
            scanf(
"%lf%lf%lf%lf",&data[i].s.x,&data[i].s.y,&data[i].e.x,&data[i].e.y);
        
for(count = 0,i = 1; i <= n;i ++)
            
for(j = i+1; j <= n; j ++)\
                
if(SEGMENTS_INTERSECT(data[i].s,data[i].e,data[j].s,data[j].e))
                    count
++;
        printf(
"%d\n",count);
    }
    
return 0;
}


感谢之前的刘 提出的意见 出现的逻辑错误 已经改正 再次谢谢


posted on 2010-04-17 11:07 付翔 阅读(1456) 评论(2)  编辑 收藏 引用 所属分类: ACM 数据结构

FeedBack:
# re: hdu 1086 计算几何入门题 [未登录]
2010-04-17 11:46 | liu
double min(double x,double y)
{
return x>y ? y:x;
}
double max(double x,double y)
{
return x>y ? y:x;
}


这地方是写重了。上面应该是?x:y  回复  更多评论
  
# re: hdu 1086 计算几何入门题 [未登录]
2010-04-17 16:53 | 付翔
@liu
谢谢 我只能说 我的程序太破 这样的程序竟然也过了   回复  更多评论
  

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



<2010年4月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜