|
先上数学证明
万物基于数学，算法也不例外  我得到的那个比值有什么用呢？ 这也就引出了根本问题，为什么要去求AO/AB？？？为什么不能求CO/CD？？？ 废话，这两个当然都嫩求，只不过在最后return的时候，对应的初始位置点不一样罢了，AO/AB，对应的就是A点，最后返回的时候A+AB*t，换成CO/CD也是一样，最后return C+CD*t
不要想着背模板，这无异于是自掘坟墓，弄懂弄透才是正道。
算法
通过上图，我们可以知道AO/AB=s▲ACD/s▲CB’D 因此我们只需要求出两个三角形的面积然后做比即可 求三角形的面积应该怎么求呢？ 这里我们采用叉积的几何意义，向量a✖向量b=a的模长✖b的模长✖sin 而我们在高中的时候学过三角形的面积=1/2absinc，两者就可以对应起来，所以我们只需要知道两个向量即可。
叉积
首先这是一个二维平面，一个向量只有x,y两个方向的分量，这样难以写成行列式进行计算，我们可以手动添上K向量，代表Z轴的方向向量。这样就可以写成一个三阶行列式。
然后我们可以在纸上推演一下，能得到这个式子，因此我们就知道两个向量的叉积的计算公式，x1y2-x2y1.
计算三角形面积
结合图片，我们要求的三角形面积为▲ACD和▲CB’D，那么有 S▲ACD=向量CA叉乘向量CD S▲CB’D=向量CD叉乘向量CB’
我们能发现CD是反复使用的，而CB’的坐标就是AB的坐标，而向量CA可以通过C点的坐标和A的坐标求得，而最后得到的交点坐标也需要在C点坐标的基础上得到。因此我们在写自定义函数的时候需要传递2个向量和2个点。
为什么能保证叉乘的结果一定是正数？
这里需要说明一下啊，笔者从来没有说过这句话，谁说叉乘的结果一定是正的？我们也不需要保证叉乘的结果一定为正，各位读者细看，我们这里用到了两次叉乘，得到的是一个比值，也就是说我们只要保证两次叉乘得到的符号相同，那么就能够确保t的值一定为正！！！别看这里就写了这么点，笔者想了好久才想到，2333，还是太菜了。
 废话不多说，直接上代码吧~
代码如下
#include
#include
using namespace std;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
//自定义函数区
Point point_read();//读入点
Vector operator - (Point,Point);//点-点=向量
Vector operator + (Point,Vector);//向量+向量=向量 点+向量=向量
Vector operator * (double,Vector);//数*向量=向量 数*点=向量
double Cross(Vector,Vector);//计算向量叉积
Point point_inter(Point,Vector,Point,Vector);
int main()
{
int T;
scanf("%d",&T);
while(T--){
//读入点的位置
Point A,B,C,D;
A=point_read();
B=point_read();
C=point_read();
D=point_read();
//计算向量
Vector AB=B-A;
Vector CD=D-C;
//判断两向量是否平行或共线
if(Cross(AB,CD)==0){
if(Cross(C-A,D-A)==0&&Cross(C-B,D-B)==0){//共线
puts("LINE");
}else{//平行
puts("NONE");
}
}else{//相交
Point ans=point_inter(A,AB,C,CD);
printf("Point is:");
printf("%.2lf %.2lf\n",ans.x,ans.y);
}
}
system("pause");
return 0;
}
Point point_read()
{
double x,y;
scanf("%lf%lf",&x,&y);
return Point(x,y);
}
Vector operator + (Point A,Vector AB)//向量+向量=向量 点+向量=向量
{
return Vector(A.x+AB.x,A.y+AB.y);
}
Vector operator - (Point A,Point B)//点-点=向量
{
return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (double k,Vector A)//数*向量=向量 数*点=向量
{
return Vector(A.x*k,A.y*k);
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
Point point_inter(Point A,Vector AB,Point C,Vector CD)
{
Vector CA=A-C;
double t=Cross(CD,CA)/Cross(AB,CD);
return Point(A+t*AB);
}
附上测试样例吧
|