当前位置: 代码迷 >> 综合 >> FZU - 2273 - Triangles - (向量相关)
  详细解决方案

FZU - 2273 - Triangles - (向量相关)

热度:73   发布时间:2024-01-12 15:20:55.0

题目链接:http://acm.fzu.edu.cn/problem.php?pid=2273

题意:给出两个三角形的三个顶点,判断两个三角形的位置关系(相交,互斥,包含)?

解析:涉及到很多向量的相关知识,用很多判断函数来判断两函数之间关系,具体见代码

向量点积:结果为数值,向量a点乘向量b=a.x*b.x+a.y*b.y=a的模*b的模*cosθ,向量间夹角为钝角返回为正,向量间夹角为直角返回为0,向量间夹角为锐角返回为负,

向量叉:结果为向量,此向量与向量a向量b所在平面垂直,

u x v = (Yu*Zv – Zu*Yv)*i + (Zu*Xv – Xu*Zv)*j + (Xu*Yv – Yu*Xv)*k;

叉积的长度 |a×b| 可以解释成这两个叉乘向量a,b共起点时,所构成平行四边形的面积。

向量a叉乘向量b=a的模*b的模*sinθ

向量的模:空间向量(x,y,z),其中x,y,z分别是三轴上的坐标,模长是:sqrt(x^2+y^2+z^2);

那么用叉乘求三角形面积:对于平面上的点a(x0,y0),b(x1,y1),c(x2,y2)构成的三角形,向量ab为(x1-x0,y1-y0),向量ac(x2-x0,y2-y0),求两向量的叉乘的模除2,即是三角形面积,二维向量a(x1,y1),b(x2,y2)扩展到三维a=(x1,y1,0),b=(x2,y2,0),则:

        | i    j   k |

a×b=|x1 y1 0 |=x1y2k-x2y1k=(x1y2-x2y1)k=(0,0,x1y2-x2y1)

        |x2 y2 0 |

那么向量ab×向量ac=(0,0,(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0))

ab×ac的模=sqrt(0^2+0^2+((x1-x0)*(y2-y0)-(x2-x0)*(y1-y0))^2)=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);

三角形面积就等于[(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0)]/2;


代码:

#include <iostream>
#include <cstdio>
#include <cmath>
typedef long long ll;
const double eps=1e-8;
struct Point
{double x,y;Point(){}Point(double xx,double yy):x(xx),y(yy){}
}a,b,c,d,e,f;//定义向量类型Vector(向量也是用坐标表示的,与Point表示方法相同)
typedef Point Vector;Vector operator - (Point A,Point B)//求向量BA
{return Vector(A.x-B.x,A.y-B.y);
}
int dcmp(double x)
{if(fabs(x)<eps)return 0;elsereturn x<0?-1:1;
}//求向量A,B的点积,向量间夹角为钝角返回为正,
//向量间夹角为直角返回为0,向量间夹角为锐角返回为负,
double Dot(Vector A,Vector B)
{return A.x*B.x+A.y*B.y;
}//求向量A,B的叉积的第三维,即(i,j,k)中的k
//如果返回为0,说明向量A,B在同一直线上
//返回为正,说明向量A,B的叉乘所得向量往上指
//返回为负,说明向量A,B的叉乘所得向量往下指
//方向遵循右手规则
double Cross(Vector A,Vector B)
{return A.x*B.y-A.y*B.x;
}//判断点p是否在直线a1a2上
bool onSeg(Point p,Point a1,Point a2)
{//如果向量pa1和向量pa2在同一直线上,且向量pa1和向量pa2夹角为钝角return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
}//判断两直线是(直线a1a2与b1b2)否相交
bool segmentProperInterection(Point a1,Point a2,Point b1,Point b2)
{if(onSeg(a1,b1,b2)||onSeg(a2,b1,b2)||onSeg(b1,a1,a2)||onSeg(b2,a1,a2))return true;double k1=Cross(a2-a1,b1-a1);double k2=Cross(a2-a1,b2-a1);double k3=Cross(b2-b1,b1-a1);double k4=Cross(b2-b1,b1-a2);//如k1,k2方向相反,则点b1、b2分别在直线a1a2的两边return dcmp(k1)*dcmp(k2)<0&&dcmp(k3)*dcmp(k4)<0;
}//判断点a,b是否为相同点
bool samePoint(Point a,Point b)
{if(a.x==b.x&&a.y==b.y) return true;return false;
}//判断两三角形是否相交
bool judge()
{if(samePoint(a,d)||samePoint(a,e)||samePoint(a,e)) return true;if(samePoint(b,d)||samePoint(b,e)||samePoint(b,e)) return true;if(samePoint(c,d)||samePoint(c,e)||samePoint(c,e)) return true;if(segmentProperInterection(a,b,d,e)) return true;if(segmentProperInterection(a,b,e,f)) return true;if(segmentProperInterection(a,b,f,d)) return true;if(segmentProperInterection(b,c,d,e)) return true;if(segmentProperInterection(b,c,e,f)) return true;if(segmentProperInterection(b,c,f,d)) return true;if(segmentProperInterection(c,a,d,e)) return true;if(segmentProperInterection(c,a,e,f)) return true;if(segmentProperInterection(c,a,f,d)) return true;return false;
}//返回向量ac,bc叉乘的第三维的方向
bool site(Point a,Point b,Point c)
{return Cross(c-a,c-b)>0;
}//判断点p是否在三角形a,b,c中
bool isContain(Point p,Point a,Point b,Point c)
{bool k=site(a,b,p);if(k!=site(b,c,p)) return false;if(k!=site(c,a,p)) return false;//如果a,b,c,共线if(Cross(c-a,c-b)==0) return false;return true;
}
int main()
{int T;scanf("%d",&T);while(T--){//a、b、c构成第一个三角形,d、e、f构成第二个三角形scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y,&e.x,&e.y,&f.x,&f.y);bool isIntersect=judge();if(isIntersect){printf("intersect\n");}else{bool a_Contain_b=isContain(d,a,b,c)&&isContain(e,a,b,c)&&isContain(f,a,b,c);bool b_Contain_a=isContain(a,d,e,f)&&isContain(b,d,e,f)&&isContain(c,d,e,f);if(a_Contain_b||b_Contain_a)printf("contain\n");elseprintf("disjoint\n");}}return 0;
}