[ACM_几何] F. 3D Triangles (三维三角行相交)

时间:2023-03-08 16:02:38

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28235#problem/A

题目大意:给出三维空间两个三角形三个顶点,判断二者是否有公共点,三角形顶点、边、内部算三角形的一部分。
解题思路:见模板
//*******************************************************************************
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stdio.h>
using namespace std;
#define eps 1e-8 int dcmp(double x){
if(fabs(x)<eps)return ;
else return x< ? -:;
} struct Point3{
double x,y,z;
Point3(double x=,double y=,double z=):x(x),y(y),z(z){}
};
bool operator==(const Point3& a,const Point3& b){
return dcmp(a.x-b.x)== && dcmp(a.y-b.y)== && dcmp(a.z-b.z)== ;
}
typedef Point3 Vector3;
Vector3 operator+(Vector3 A,Vector3 B){
return Vector3(A.x+B.x,A.y+B.y,A.z+B.z);
}
Vector3 operator-(Vector3 A,Vector3 B){
return Vector3(A.x-B.x,A.y-B.y,A.z-B.z);
}
Vector3 operator*(Vector3 A,double p){
return Vector3(A.x*p,A.y*p,A.z*p);
}
Vector3 operator/(Vector3 A,double p){
return Vector3(A.x/p,A.y/p,A.z/p);
} double Dot(Vector3 A,Vector3 B){return A.x*B.x+A.y*B.y+A.z*B.z;}
double Length(Vector3 A){return sqrt(Dot(A,A));}
double Angle(Vector3 A,Vector3 B){return acos(Dot(A,B)/Length(A)/Length(B));} /*p到平面p0-n的距离
double DistanceToPlane(Point3 p,Point3 p0,Vector3 n){
return fabs(Dot(p-p0,n))/Length(n);
}
//p到平面p0-n的投影
Point3 GetPlaneProjection(Point3 p,Point3 p0,Vector3 n){
double d=Dot(p-p0,n)/Length(n);
return p+n*d;
}
//直线p1-p2到平面p0-n的交点
Point3 LinePlaneIntersection(Point3 p1,Point3 p2,Point3 p0,Vector3 n){
Vector3 v=p2-p1;
double t=(Dot(n,p0-p1)/Dot(n,p2-p1));//判断分母是否为0
return p1+v*t;//如果是线段,判断t是不是在0-1之间
}*/ //叉积
Vector3 Cross(Vector3 A,Vector3 B){
return Vector3(A.y*B.z-A.z*B.y,A.z*B.x-A.x*B.z,A.x*B.y-A.y*B.x);
}
double Area2(Point3 A,Point3 B,Point3 C){return Length(Cross(B-A,C-A));}
//点p在三角形p0p1p2中(利用面积法算点是否在三角形内,假定所有的点共面)
bool PointInTri(Point3 p,Point3 p0,Point3 p1,Point3 p2){
double area1=Area2(p,p0,p1);
double area2=Area2(p,p1,p2);
double area3=Area2(p,p2,p0);
return dcmp(area1+area2+area3-Area2(p0,p1,p2))==;
}
//三角形p0p1p2是否和线段AB相交(此函数会把线段在平面上的情况视为不相交)
bool TriSegIntersection(Point3 p0,Point3 p1,Point3 p2,Point3 A,Point3 B,Point3& p){
Vector3 n=Cross(p1-p0,p2-p0);
if(dcmp(Dot(n,B-A))==)return false;//平行或共面
else{ //直线AB和平面P0P1P2有唯一交点
double t=Dot(n,p0-A)/Dot(n,B-A);
if(dcmp(t)< || dcmp(t-)>)return false;//交点不在线段AB上
p=A+(B-A)*t; //计算交点
return PointInTri(p,p0,p1,p2); //判断交点是否在三角形内
}
}
/*到直线的距离
double DistanceToLine(Point3 p,Point3 A,Point3 B){
Vector3 v1=B-A,v2=p-A;
return Length(Cross(v1,v2))/Length(v1);
}
//点p到线段AB的距离
double DistanceToSegment(Point3 p,Point3 A,Point3 B){
if(A==B)return Length(p-A);
Vector3 v1=B-A,v2=p-A,v3=p-B;
if(dcmp(Dot(v1,v2))<0)return Length(v2);
else if(dcmp(Dot(v1,v3))>0)return Length(v3);
else return Length(Cross(v1,v2))/Length(v1);
}
//返回,,的混合积,他等于四面体邮箱面积的6倍
double Volume6(Point3 A,Point3 B,Point3 C,Point3 D){
return Dot(D-A,Cross(B-A,C-A));
}*/
//判断两个三角形是否有公共点
bool TriTriIntersection(Point3* T1,Point3* T2){
Point3 p;
for(int i=;i<;i++){
if(TriSegIntersection(T1[],T1[],T1[],T2[i],T2[(i+)%],p))return true;
if(TriSegIntersection(T2[],T2[],T2[],T1[i],T1[(i+)%],p))return true;
}
return false;
}
//*******************************************************************************
int main(){
int T;cin>>T;
while(T--){
Point3 T1[],T2[];
for(int i=;i<;i++)cin>>T1[i].x>>T1[i].y>>T1[i].z;
for(int i=;i<;i++)cin>>T2[i].x>>T2[i].y>>T2[i].z;
cout<<(TriTriIntersection(T1,T2) ? "1\n":"0\n");
}return ;
}
//*******************************************************************************