分析:判断两直线是否相交:
分两步:
①:快速排斥实验
设以线段P1P2为对角线的矩形为R,以线段Q1Q2为对角线的矩形为T,如果R和T不相交,显然两线段不会相交。
②:跨立实验
如果两直线相交,则两直线必然相互跨立对方。若P1P2跨立Q1Q2,则矢量(P1-Q1)和(P2-Q1)位于矢量(Q2-Q1)的两侧,
即(P1-Q1)X(Q2-Q1)*(P2-Q1)X(Q2-Q1)<0. 上式可改写为
(P1-Q1)X(Q2-Q1)*(Q2-Q1)X(P2-Q1)>0. 当(P1-Q1)X(Q2-Q1)=0 时,说明(P1-Q1)和(Q2-Q1)共线,但因为已经通过快速排斥实验,所以
P1一定在线段Q1Q2上,同理,(Q2-Q1)X(P2-Q1)=0 说明P2一定在直线Q1Q2上。所以判断P1P2跨立Q1Q2的依据是:
(P1 - Q1) X (Q2 - Q1) * (Q2 - Q1) X (P2 -Q1)>=0
#include <cstdio>
struct node{double x0,y0,x1,y1;}q[101];
int p(struct node a,struct node b){
double k1=(a.x0-b.x0)*(b.y1-b.y0)-(a.y0-b.y0)*(b.x1-b.x0);
double k2=(b.x1-b.x0)*(a.y1-b.y0)-(b.y1-b.y0)*(a.x1-b.x0);
if(k1*k2>=0)return 1; return 0;
}
int main(){
int t,tot=0,i,j;
while(scanf("%d",&t),t){
for(i=0;i<t;i++)scanf("%lf%lf%lf%lf",&q[i].x0,&q[i].y0,&q[i].x1,&q[i].y1);
for(i=0;i<t-1;i++)
for(j=i+1;j<t;j++)tot+=(p(q[i],q[j])&&p(q[j],q[i]));
printf("%d
",tot); tot=0;
}
return 0;
}