#include <iostream>
using namespace std;


/*求兩條線段是否相交首先要求兩條線段通過快速排斥實驗，即做出能包含兩條線段的最小的矩形，既是以兩條線段作為對角線的
兩個矩形，判斷兩個矩形是否相交，若兩個矩形不能同時在x方向和y方向相交，則兩條線段不可能相交，通過了快速排斥實驗后再
判斷兩條線段是否互相跨立，既是一條線段的兩個端點是否在另一條線段所在直線的兩側，若滿足以上兩條，則線段一定相交*/

typedef struct
{
        double x;
        double y;
        }Coordinate;
        
typedef struct
{
        Coordinate start;
        Coordinate end; 
        }Line;
 
int main()
{
      Line a,b;
      Coordinate m,n,p;
      double x,y;
      bool tag;
      cout<<"請輸入兩條線段的坐標:"<<endl;
      cin>>a.start.x>>a.start.y>>a.end.x>>a.end.y;
      cin>>b.start.x>>b.start.y>>b.end.x>>b.end.y;
      //先判斷兩矩形是否在x方向上相交
      //若要在x方向上相交，則滿足end1.x>start2.x,start1.x<end2.x
      if(a.end.x>=b.start.x&&a.start.x<=b.end.x)
      tag=true;
      else
      tag=false;
      
      if(tag==false)
      {
           cout<<"兩條線段不相交!"<<endl;
                system("pause");
           return 0;         
                    }
     //現在判斷y方向上是否相交
     //若要在y方向上相交，則滿足end1.y>start2.y,start1.y<end2.y
     if(a.end.y>=b.start.y&&a.start.y<=b.end.y)               
     tag=true;
     else
     tag=false;
     
     if(tag==false)
     {
        cout<<"兩條線段不相交!"<<endl;
             system("pause");
        return 0;           
                   }
     
     //通過了快速排斥實驗后，就使用叉積來判斷是否跨立的問題 
     
     //先判斷a是否跨立b
     //用a的起點分別與b的兩端連成的兩條線段與a求叉積，若兩條線段分別在a的順時針與逆時針方向，則a跨立b
     //若在同一側，則不跨立，兩條線段不相交
     m.x=b.start.x-a.start.x;
     m.y=b.start.y-a.start.y;
     n.x=b.end.x-a.start.x;
     n.y=b.end.y-a.start.y;
     p.x=a.end.x-a.start.x;
     p.y=a.end.y-a.start.y;
     x=m.x*p.y-m.y*p.x;
     y=n.x*p.y-n.y*p.x;
     if(x*y<=0)
     tag=true;
     else
     tag=false;
     if(tag==false)
     {
        cout<<"兩條線段不相交!"<<endl;
             system("pause");
        return 0; 
                   }
     //現在判斷b是否跨立a
  
     m.x=a.start.x-b.start.x;
     m.y=a.start.y-b.start.y;
     n.x=a.end.x-b.start.x;
     n.y=a.end.y-b.start.y;
     p.x=b.end.x-b.start.x;
     p.y=b.end.y-b.start.y;
     x=m.x*p.y-m.y*p.x;
     y=m.y*p.x-m.x*p.y;
  
     if(x*y<=0)
     tag=true;
     else
     tag=false;
     if(tag==false)
     {
         cout<<"兩條線段不相交!"<<endl;
              system("pause");
         return 0;          
                   }
                   
   cout<<"兩條線段相交!"<<endl;                                   
     system("pause");
     return 0;                                  
}