这是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 ? y:x;
}
double max(double x,double y)
{
return x<y ? 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
付翔 阅读(1466)
评论(2) 编辑 收藏 引用 所属分类:
ACM 数据结构