学步园

原理：

我们分两步确定两条线段是否相交：
(1)．快速排斥试验

设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交；

(2)．跨立试验
如果两线段相交，则两线段必然相互跨立对方，P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即
( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0
上式可改写成
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
当( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；
同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。
所以判断P1P2跨立Q1Q2的依据是：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0
同理判断Q1Q2跨立P1P2的依据是：

( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) ≥ 0

Code：

#include<stdio.h>
#include<math.h>
#define N 4
 
typedef struct
{
    int x;
    int y;
}node;
 
int max(int x,int y)
{
    return x>y?x:y;
}
 
int min(int x,int y)
{
    return x<y?x:y;
}
int fun(node a,node b,node c,node d)
{
    node p[3];
    int flag,m,n;
    p[0].x=b.x-a.x;
    p[0].y=b.y-a.y;
    p[1].x=c.x-a.x;
    p[1].y=c.y-a.y;
    p[2].x=d.x-a.x;
    p[2].y=d.y-a.y;
    m=(p[0].x*p[1].y-p[0].y*p[1].x);
    n=(p[0].x*p[2].y-p[0].y*p[2].x);
    if((m%1000)!=0)
        m=m%1000;
    else
    {
        while(fabs(m/10)>10)
            m=m/10;
    }
    if((n%1000)!=0)
        n=n%1000;
    else
    {
        while(fabs(n/10)>10)
            n=n/10;
    }
    if(n*m<0)
        flag=1;
    else if(m*n==0)
    {
        if((c.x>=min(a.x,b.x)&&c.x<=max(a.x,b.x))&&(c.y>=min(a.y,b.y)&&c.y<=max(a.y,b.y))||(d.x>=min(a.x,b.x)&&d.x<=max(a.x,b.x))&&(d.y>=min(a.y,b.y)&&d.y<=max(a.y,b.y)))
            flag=0;
        else
            flag=-1;
    }
    else
        flag=-1;
    return flag;
}
 
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i;
        for(i=0;i<n;i++)
        {
            int i,flag1,flag2;
            node p[N];
            for(i=0;i<N;i++)
               scanf("%ld%ld",&p[i].x,&p[i].y);
            flag1=fun(p[0],p[1],p[2],p[3]);
            flag2=fun(p[2],p[3],p[0],p[1]);
            if((flag1==1&&flag2==1)||flag1==0||flag2==0||(flag1==0&&flag2==0))
               printf("intersect\n");
            else
               printf("disjoint\n");
        }
    }
    return 0;
}