線段相交模板，線段相交

線段相交模板，線段相交

線段P1P2與線段Q1Q2是否有交點。P1P2要與Q1Q2相交，則點P1和點P2就得在線段Q1Q2的兩側(同理點Q1和點Q2就得在線段P1P2的兩側)。用直線的叉積來求解。即：

(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)>=0 且 (Q1-P1)×(P2-P1)*(P2-P1)×(Q2-P1)>=0  (ps:"×"表示叉乘)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=100;
struct Node
{
    double x;
    double y;
};
double Product(Node a,Node b) //叉積
{
    return a.x*b.y-b.x*a.y;
}
bool Intersect(Node P1,Node P2,Node Q1,Node Q2)
{
    Node a[4],b[4];
    a[0].x=P1.x-Q1.x;a[0].y=P1.y-Q1.y;
    b[0].x=Q2.x-Q1.x;b[0].y=Q2.y-Q1.y;
    a[1]=b[0];
    b[1].x=P2.x-Q1.x;b[1].y=P2.y-Q1.y;

    a[2].x=Q1.x-P1.x;a[2].y=Q1.y-P1.y;
    b[2].x=P2.x-P1.x;b[2].y=P2.y-P1.y;
    a[3]=b[2];
    b[3].x=Q2.x-P1.x;b[3].y=Q2.y-P1.y;
    if(Product(a[0],b[0])*Product(a[1],b[1])>=0 && Product(a[2],b[2])*Product(a[3],b[3])>=0)
        return true; //(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)>=0 && (Q1-P1)×(P2-P1)*(P2-P1)×(Q2-P1)>=0
    return false;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    Node A1,A2,B1,B2;
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&A1.x,&A1.y,&A2.x,&A2.y,&B1.x,&B1.y,&B2.x,&B2.y);
    if(Intersect(A1,A2,B1,B2))
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}