#include <iostream>
#include <cmath>
using namespace std;
struct POINTF {float x; float y;};
bool Equal(float f1, float f2) {
  return (abs(f1 - f2) < 1e-4f);
}
//判斷兩點是否相等
bool operator==(const POINTF &p1, const POINTF &p2) {
  return (Equal(p1.x, p2.x) && Equal(p1.y, p2.y));
}
//比較兩點坐標(biāo)大小，先比較x坐標(biāo)，若相同則比較y坐標(biāo)
bool operator>(const POINTF &p1, const POINTF &p2) {
  return (p1.x > p2.x || (Equal(p1.x, p2.x) && p1.y > p2.y));
}
//計算兩向量外積
float operator^(const POINTF &p1, const POINTF &p2) {
  return (p1.x * p2.y - p1.y * p2.x);
}
//判定兩線段位置關(guān)系，并求出交點(如果存在)。返回值列舉如下：
//[有重合] 完全重合(6)，1個端點重合且共線(5)，部分重合(4)
//[無重合] 兩端點相交(3)，交于線上(2)，正交(1)，無交(0)，參數(shù)錯誤(-1)
int Intersection(POINTF p1, POINTF p2, POINTF p3, POINTF p4, POINTF &Int) {
  //保證參數(shù)p1!=p2，p3!=p4
  if (p1 == p2 || p3 == p4) {
    return -1; //返回-1代表至少有一條線段首尾重合，不能構(gòu)成線段
  }
  //為方便運算，保證各線段的起點在前，終點在后。
  if (p1 > p2) {
    swap(p1, p2);
  }
  if (p3 > p4) {
    swap(p3, p4);
  }
  //判定兩線段是否完全重合
  if (p1 == p3 && p2 == p4) {
    return 6;
  }
  //求出兩線段構(gòu)成的向量
  POINTF v1 = {p2.x - p1.x, p2.y - p1.y}, v2 = {p4.x - p3.x, p4.y - p3.y};
  //求兩向量外積，平行時外積為0
  float Corss = v1 ^ v2;
  //如果起點重合
  if (p1 == p3) {
    Int = p1;
    //起點重合且共線(平行)返回5；不平行則交于端點，返回3
    return (Equal(Corss, 0) ? 5 : 3);
  }
  //如果終點重合
  if (p2 == p4) {
    Int = p2;
    //終點重合且共線(平行)返回5；不平行則交于端點，返回3
    return (Equal(Corss, 0) ? 5 : 3);
  }
  //如果兩線端首尾相連
  if (p1 == p4) {
    Int = p1;
    return 3;
  }
  if (p2 == p3) {
    Int = p2;
    return 3;
  }//經(jīng)過以上判斷，首尾點相重的情況都被排除了
  //將線段按起點坐標(biāo)排序。若線段1的起點較大，則將兩線段交換
  if (p1 > p3) {
    swap(p1, p3);
    swap(p2, p4);
    //更新原先計算的向量及其外積
    swap(v1, v2);
    Corss = v1 ^ v2;
  }
  //處理兩線段平行的情況
  if (Equal(Corss, 0)) {
    //做向量v1(p1, p2)和vs(p1,p3)的外積，判定是否共線
    POINTF vs = {p3.x - p1.x, p3.y - p1.y};
    //外積為0則兩平行線段共線，下面判定是否有重合部分
    if (Equal(v1 ^ vs, 0)) {
      //前一條線的終點大于后一條線的起點，則判定存在重合
      if (p2 > p3) {
        Int = p3;
        return 4; //返回值4代表線段部分重合
      }
    }//若三點不共線，則這兩條平行線段必不共線。
    //不共線或共線但無重合的平行線均無交點
    return 0;
  } //以下為不平行的情況，先進(jìn)行快速排斥試驗
  //x坐標(biāo)已有序，可直接比較。y坐標(biāo)要先求兩線段的最大和最小值
  float ymax1 = p1.y, ymin1 = p2.y, ymax2 = p3.y, ymin2 = p4.y;
  if (ymax1 < ymin1) {
    swap(ymax1, ymin1);
  }
  if (ymax2 < ymin2) {
    swap(ymax2, ymin2);
  }
  //如果以兩線段為對角線的矩形不相交，則無交點
  if (p1.x > p4.x || p2.x < p3.x || ymax1 < ymin2 || ymin1 > ymax2) {
    return 0;
  }//下面進(jìn)行跨立試驗
  POINTF vs1 = {p1.x - p3.x, p1.y - p3.y}, vs2 = {p2.x - p3.x, p2.y - p3.y};
  POINTF vt1 = {p3.x - p1.x, p3.y - p1.y}, vt2 = {p4.x - p1.x, p4.y - p1.y};
  float s1v2, s2v2, t1v1, t2v1;
  //根據(jù)外積結(jié)果判定否交于線上
  if (Equal(s1v2 = vs1 ^ v2, 0) && p4 > p1 && p1 > p3) {
    Int = p1;
    return 2;
  }
  if (Equal(s2v2 = vs2 ^ v2, 0) && p4 > p2 && p2 > p3) {
    Int = p2;
    return 2;
  }
  if (Equal(t1v1 = vt1 ^ v1, 0) && p2 > p3 && p3 > p1) {
    Int = p3;
    return 2;
  }
  if (Equal(t2v1 = vt2 ^ v1, 0) && p2 > p4 && p4 > p1) {
    Int = p4;
    return 2;
  } //未交于線上，則判定是否相交
  if(s1v2 * s2v2 > 0 || t1v1 * t2v1 > 0) {
    return 0;
  } //以下為相交的情況，算法詳見文檔
  //計算二階行列式的兩個常數(shù)項
  float ConA = p1.x * v1.y - p1.y * v1.x;
  float ConB = p3.x * v2.y - p3.y * v2.x;
  //計算行列式D1和D2的值，除以系數(shù)行列式的值，得到交點坐標(biāo)
  Int.x = (ConB * v1.x - ConA * v2.x) / Corss;
  Int.y = (ConB * v1.y - ConA * v2.y) / Corss;
  //正交返回1
  return 1;
}
//主函數(shù)
int main(void) {
  //隨機生成100個測試數(shù)據(jù)
  for (int i = 0; i < 100; ++i) {
    POINTF p1, p2, p3, p4, Int;
    p1.x = (float)(rand() % 10); p1.y = (float)(rand() % 10);
    p2.x = (float)(rand() % 10); p2.y = (float)(rand() % 10);
    p3.x = (float)(rand() % 10); p3.y = (float)(rand() % 10);
    p4.x = (float)(rand() % 10); p4.y = (float)(rand() % 10);
    int nr = Intersection(p1, p2, p3, p4, Int);
    cout << "[(";
    cout << (int)p1.x << ',' << (int)p1.y << "),(";
    cout << (int)p2.x << ',' << (int)p2.y << ")]--[(";
    cout << (int)p3.x << ',' << (int)p3.y << "),(";
    cout << (int)p4.x << ',' << (int)p4.y << ")]: ";
    cout << nr;
    if (nr > 0) {
      cout << '(' << Int.x << ',' << Int.y << ')';
    }
    cout << endl;
  }
  return 0;
}