两条直线的交点（叉积）

/*在两条直线相交时，求相交点
 方法1：可以直线方程来求解，但是效率低下，而且程序繁琐。
 方法2：使用叉积公式求交点，即高效又简便。

  介绍方法2：
    设mul(p1,p2,p0)为p1p0与p0p1的叉积，即mul(p1,p2,p0)=(p1-p0)^(p2-p0)。
    该叉积可以看做由点p0,p1,p2和p1+p2四个点围成的平行四边形的阴影面积，
  即三角形p1p2p0面积s(p1p2p0)=mul(p1,p2,p0)/2;

    四边形ABCD,线段AB与CD交于点P。从D点出发引一条AB的垂线DD'，从C点出发引一条AB的垂线CC'，
  由于三角形DD'P与三角形CC'P相似，因此|DD'|/|CC'|=|DP|/|PC|;由因为S(ABD)=(DD'*AB)/2,
  S(ABC)=(CC'*AB)/2;
  ==>|DP|/|PC|=S(ABD)/S(ABC)=|AD*AB|/|AC*AB|=|mul(D,B,A)|/|mul(C,B,A)|
  又因为|DP|/|PC|=(x(D)-x(P))/(x(P)-x(C))=(y(D)-y(P))/(y(P)-y(C));
  x(p)=(S(ABD)*x(C)+S(ABC)*x(D))/(S(ABD)+S(ABC))
      =(mul(D,B,A)*x(C)-mul(C,B,A)*x(D))/mul(D,C,A)-mul(C,B,A);
  x(p)=(S(ABD)*y(C)+S(ABC)*y(D))/(S(ABD)+S(ABC))
      =(mul(D,B,A)*y(C)-mul(C,B,A)*y(D))/mul(D,C,A)-mul(C,B,A);
*/

/* poj 1269
例子：
Sample Input
5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5
Sample Output
INTERSECTING LINES OUTPUT
POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
END OF OUTPUT
解题思路：
计算a1=mul(p1,p2,p3) a2=mul(p1,p2,p4);
若a1==0&&a2==0,则重叠
若a1与a2同号，两者平行
若a1与a2异号，相交
 p=((a2*p3.x-a1*p4.x)/(a2-a1),(a2*p3.y-a1*p4.y)/(a2-a1));
*/
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const double epsi=1e-10;
struct Point
{
 double x,y;
 Point(double _x=0,double _y=0):x(_x),y(_y){}
 Point operator -(const Point &op) const
 {
  return Point(x-op.x,y-op.y);
 }
 double operator ^(const Point &op) const
 {
  return x*op.y-y*op.x;
 }
};
inline int sign(const double &x)
{
 if(x>epsi) return 1;
 if(x<-epsi) return -1;
 return 0;
}
inline double sqr( const double &x)
{
 return x*x;
}
inline double dis(const Point &p1,const Point &p2)
{
 return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}
inline double mul(const Point &p0,const Point &p1,const Point &p2)
{
 return (p1-p0)^(p2-p0);
}
inline int cross(const Point &p1,const Point &p2,const Point &p3,const Point &p4,Point &p)
{
 double a1=mul(p1,p2,p3),a2=mul(p1,p2,p4);
 if(sign(a1)==0&&sign(a2)==0) return 2;//重叠
 if(sign(a1-a2)==0) return 0;//平行
 p.x=(a2*p3.x-a1*p4.x)/(a2-a1);
 p.y=(a2*p3.y-a1*p4.y)/(a2-a1);
 return 1;//相交
}
Point p1,p2,p3,p4,p;
int main()
{
 int test=0;
 printf("INTERSECTING LINES OUTPUT\n");
 scanf("%d",&test);
 while(test--)
 {
  scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y,&p3.x,&p3.y,&p4.x,&p4.y);
  int fm=cross(p1,p2,p3,p4,p);
  if(fm==0) printf("NONE\n");
        else if(fm==2) printf("LINE\n");
  else printf("POINT %.2lf %.2lf\n",p.x,p.y);
 }
 printf("END OF OUTPUT\n");
 return 0;
}