uva11275简单三维几何

链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=538&page=show_problem&problem=2250

题意：判断两个空间三角形是否相交

思路：恩恩，就判断一下。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn=1000;
const double eps=1e-8;

struct Point3
{
    double x,y,z;
    Point3(double x=0,double y=0,double z=0):x(x),y(y),z(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);
}
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}
bool operator == (const Point3& a,const Point3& b)//两点相等
{
    return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0 && dcmp(a.z-b.z)==0;
}
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));
}
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));
}
bool PointInTri(Point3 P,Point3 P0,Point3 P1,Point3 P2)
{
    //点P在三角形P0P1P2中,假定P在三角形的平面内
    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))==0;
}
bool TriSegIntersection(Point3 P0,Point3 P1,Point3 P2,Point3 A,Point3 B,Point3& P)
{
    //三角形是否和线段AB相交
    Vector3 n=Cross(P1-P0,P2-P0);
    if(dcmp(Dot(n,B-A))==0) return false;
    else
    {
        double t=Dot(n,P0-A)/Dot(n,B-A);//线段和平面相交的参数
        if(dcmp(t)<0 || dcmp(t-1)>0) return false;//交点不在线段上
        P=A+(B-A)*t;//计算线段和平面的交点
        return PointInTri(P,P0,P1,P2);//判断交点是否在三角形内
    }
}
Point3 read()
{
    Point3 p;
    double x,y,z;
    scanf("%lf%lf%lf",&x,&y,&z);
    return p=Point3(x,y,z);
}

Point3 t1[3],t2[3];

bool solve()
{
    Point3 p;
    for(int i=0; i<3; i++)
    {
        if(TriSegIntersection(t1[0],t1[1],t1[2],t2[i],t2[(i+1)%3],p))
            return true;
        if(TriSegIntersection(t2[0],t2[1],t2[2],t1[i],t1[(i+1)%3],p))
            return true;
    }
    return false;
}

int main()
{
//    freopen("in.cpp","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0; i<3; i++)
            t1[i]=read();
        for(int i=0; i<3; i++)
            t2[i]=read();;
        if(solve()==1) printf("1
");
        else printf("0
");
    }
    return 0;
}