算法简单说明:
首先判断以两条线段为对角线的矩形是否相交,如果不相交两条线段肯定也不相交。
(所谓以a1b2为对角钱的矩形就是以两边长为|a1.x – b2.x|和|a1.y – b2.y|以及a1b2为对角线的矩形)。
如果相交的话,利用矢量叉乘判断两条线段是否相互跨越,如果相互跨越显然就相交,反之则不相交。算法不难,但是一些特殊情况需要考虑到,比如两条相段共线且在断点处相交。下面的代码经过测试了,应该没有bug,如果你真的发现了bug请告诉我:)
/******************************************************** * *
* 返回(P1-P0)*(P2-P0)的叉积。 *
* 若结果为正,则<P0,P1>在<P0,P2>的顺时针方向; *
* 若为0则<P0,P1><P0,P2>共线; *
* 若为负则<P0,P1>在<P0,P2>的在逆时针方向; *
* 可以根据这个函数确定两条线段在交点处的转向, *
* 比如确定p0p1和p1p2在p1处是左转还是右转,只要 *
* 求(p2-p0)*(p1-p0),若<0则左转,>0则右转,=0则 *
* 共线 *
* *
\********************************************************/
float multiply(TPoint p1,TPoint p2,TPoint p0)
{
return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}
#include<stdio.h>
#include<stdlib.h>
typedef struct T
{
double x,y;
} point;
double judge( point p1,point p2, point p )//判断点是否在直线的两边
{
return ( p1.x-p.x )*( p2.y-p.y )-( p2.x-p.x )*( p1.y-p.y );
}
bool on_segments( point p1, point p2, point p )//判断端点是不是在直线上
{
double max=p1.x>p2.x?p1.x:p2.x;//找出直线的左右端点的范围
double min=p1.x<p2.x?p1.x:p2.x;
if( p.x>=min&&p.x<=max ) return true;
else return false;
}
bool segments( point p1,point p2,point q1,point q2 )
{
double d1=judge( p1, p2, q1 );
double d2=judge( p1, p2, q2 );
double d3=judge( q1, q2, p1 );
double d4=judge( q1, q2 ,p2 );
if( d1*d2<0&&d3*d4<0 ) return true;
if( d1==0 && on_segments( p1,p2,q1 ) ) return true;//d为0是平行的情况,这是我们就要考虑是不是端点在直线上
if( d2==0 && on_segments( p1,p2,q2 ) ) return true ;
if( d3==0 && on_segments( q1,q2,p1 ) ) return true;
if( d4==0 && on_segments( q1,q2,p2 ) ) return true;
return false;
}
int main()
{
point start[124],end[124];
int n;
while( scanf("%d",&n),n )
{
int sum=0;
for( int i=1; i<=n; i++ )
{
scanf( "%lf%lf%lf%lf",&start[i].x,&start[i].y,&end[i].x,&end[i].y );
}
for( int i=1; i<=n; i++ )
for( int j=i+1; j<=n; j++ )
{
if( segments( start[i],end[i],start[j],end[j] ) )
sum++;
}
printf( "%d\n",sum );
}
return 0;
}