uva 11275 3D Triangles (3D-Geometry)

uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2250
　　判断两个空间中的三角形是否有公共点。
代码如下：
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <vector>
  5 #include <iostream>
  6 #include <algorithm>
  7 
  8 using namespace std;
  9 
 10 struct Point3 {
 11     double x[3];
 12     Point3() {}
 13     Point3(double *_x) { for (int i = 0; i < 3; i++) x[i] = _x[i];}
 14 } ;
 15 typedef Point3 Vec3;
 16 
 17 Vec3 operator + (Vec3 a, Vec3 b) {
 18     Vec3 ret;
 19     for (int i = 0; i < 3; i++) ret.x[i] = a.x[i] + b.x[i];
 20     return ret;
 21 }
 22 Vec3 operator - (Vec3 a, Vec3 b) {
 23     Vec3 ret;
 24     for (int i = 0; i < 3; i++) ret.x[i] = a.x[i] - b.x[i];
 25     return ret;
 26 }
 27 Vec3 operator * (Vec3 a, double p) {
 28     Vec3 ret;
 29     for (int i = 0; i < 3; i++) ret.x[i] = a.x[i] * p;
 30     return ret;
 31 }
 32 Vec3 operator / (Vec3 a, double p) {
 33     Vec3 ret;
 34     for (int i = 0; i < 3; i++) ret.x[i] = a.x[i] / p;
 35     return ret;
 36 }
 37 
 38 const double EPS = 1e-8;
 39 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
 40 
 41 bool operator < (Point3 a, Point3 b) {
 42     for (int i = 0; i < 3; i++) {
 43         if (sgn(a.x[i] - b.x[i])) return a.x[i] < b.x[i];
 44     }
 45     return true;
 46 }
 47 bool operator == (Point3 a, Point3 b) {
 48     for (int i = 0; i < 3; i++) {
 49         if (sgn(a.x[i] - b.x[i])) return false;
 50     }
 51     return true;
 52 }
 53 
 54 double dotDet(Vec3 a, Vec3 b) {
 55     double ret = 0.0;
 56     for (int i = 0; i < 3; i++) ret += a.x[i] * b.x[i];
 57     return ret;
 58 }
 59 inline double dotDet(Point3 o, Point3 a, Point3 b) { return dotDet(a - o, b - o);}
 60 inline Vec3 crossDet(Vec3 a, Vec3 b) {
 61     Vec3 ret;
 62     for (int i = 0; i < 3; i++) ret.x[i] = a.x[(i + 1) % 3] * b.x[(i + 2) % 3] - b.x[(i + 1) % 3] * a.x[(i + 2) % 3];
 63     return ret;
 64 }
 65 inline Vec3 crossDet(Point3 o, Point3 a, Point3 b) { return crossDet(a - o, b - o);}
 66 inline double vecLen(Vec3 x) { return sqrt(dotDet(x, x));}
 67 inline double angle(Vec3 a, Vec3 b) { return acos(dotDet(a, b) / vecLen(a) / vecLen(b));}
 68 inline double ptDis(Point3 a, Point3 b) { return vecLen(a - b);}
 69 inline double triArea(Point3 a, Point3 b, Point3 c) { return vecLen(crossDet(a, b, c));}
 70 inline Vec3 vecUnit(Vec3 x) { return x / vecLen(x);}
 71 
 72 struct Plane {
 73     Point3 p;
 74     Vec3 n;
 75     Plane() {}
 76     Plane(Point3 p, Vec3 n) : p(p), n(n) {}
 77     Plane(Point3 a, Point3 b, Point3 c) { p = a; n = crossDet(b - a, c - a);}
 78 } ;
 79 inline double pt2Plane(Point3 p, Point3 p0, Vec3 n) { return dotDet(p - p0, n) / vecLen(n);}
 80 inline double pt2Plane(Point3 p, Plane P) { return pt2Plane(p, P.p, P.n);}
 81 inline Point3 ptOnPlane(Point3 p, Point3 p0, Vec3 n) { return p + n * pt2Plane(p, p0, n);}
 82 inline Point3 ptOnPlane(Point3 p, Plane P) { return ptOnPlane(p, P.p, P.n);}
 83 inline bool ptInPlane(Point3 p, Point3 p0, Vec3 n) { return sgn(dotDet(p - p0, n)) == 0;}
 84 inline bool ptInPlane(Point3 p, Plane P) { return ptInPlane(p, P.p, P.n);}
 85 
 86 int linePlaneIntersect(Point3 s, Point3 t, Point3 p0, Vec3 n, Point3 &x) {
 87     double res1 = dotDet(n, p0 - s);
 88     double res2 = dotDet(n, t - s);
 89     if (sgn(res2) == 0) {
 90         if (ptInPlane(s, p0, n)) return 2;
 91         return 0;
 92     }
 93     x = s + (t - s) * (res1 / res2);
 94     return 1;
 95 }
 96 
 97 bool ptInTri(Point3 p, Point3 *tri) {
 98     double area = triArea(tri[0], tri[1], tri[2]);
 99     double sum = 0.0;
100     for (int i = 0; i < 3; i++) sum += triArea(p, tri[i], tri[(i + 1) % 3]);
101     return sgn(sum - area) == 0;
102 }
103 
104 bool triSegIntersect(Point3 *tri, Point3 s, Point3 t) {
105     Vec3 n = crossDet(tri[0], tri[1], tri[2]);
106     if (sgn(dotDet(n, t - s)) == 0) return false;
107     else {
108         double k = dotDet(n, tri[0] - s) / dotDet(n, t - s);
109         if (sgn(k) < 0 || sgn(k - 1) > 0) return false;
110         Point3 x = s + (t - s) * k;
111         return ptInTri(x, tri);
112     }
113 }
114 
115 Point3 tri[2][3];
116 
117 bool check() {
118     for (int i = 0; i < 2; i++) {
119         for (int j = 0; j < 3; j++) {
120             if (triSegIntersect(tri[i], tri[i ^ 1][j], tri[i ^ 1][(j + 1) % 3])) return true;
121         }
122     }
123     return false;
124 }
125 
126 int main() {
127 //    freopen("in", "r", stdin);
128     int n;
129     cin >> n;
130     while (n--) {
131         for (int i = 0; i < 2; i++) {
132             for (int j = 0; j < 3; j++) {
133                 for (int k = 0; k < 3; k++) {
134                     cin >> tri[i][j].x[k];
135                 }
136             }
137         }
138         cout << check() << endl;
139     }
140     return 0;
141 }
View Code
——written by Lyon