這是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
付翔 閱讀(1483)
評論(2) 編輯 收藏 引用 所屬分類:
ACM 數據結構