三维几何，题意是要求求出两条空间线段的距离。题目难度在于要求用有理数的形式输出，这就要求写一个有理数类了。
开始的时候写出来的有理数类就各种疯狂乱套，TLE的结果是显然的。后来发现，在计算距离前都是不用用到有理数类的，所以就将开始的部分有理数改成直接用long long。其实好像可以用int来做的，不过我的方法比较残暴，中间运算过程居然爆int了。所以就只好用long long了。
代码如下，附带debug以及各种强的数据：
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 7 using namespace std; 8 9 template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a;} 10 template <class T> T sqr(T x) { return x * x;} 11 typedef long long LL; 12 struct Rat { 13 LL a, b; 14 Rat() {} 15 Rat(LL x) { a = x, b = 1;} 16 Rat(LL _a, LL _b) { 17 LL GCD = gcd(_b, _a); 18 a = _a / GCD, b = _b / GCD; 19 } 20 double val() { return (double) a / b;} 21 bool operator < (Rat x) const { return a * x.b < b * x.a;} 22 bool operator > (Rat x) const { return a * x.b > b * x.a;} 23 bool operator == (Rat x) const { return a * x.b == b * x.a;} 24 bool operator < (LL x) const { return Rat(a, b) < Rat(x);} 25 bool operator > (LL x) const { return Rat(a, b) > Rat(x);} 26 bool operator == (LL x) const { return Rat(a, b) == Rat(x);} 27 Rat operator + (Rat x) { 28 LL tb = b * x.b, ta = a * x.b + b * x.a; 29 LL GCD = gcd(abs(tb), abs(ta)); 30 return Rat(ta / GCD, tb / GCD); 31 } 32 Rat operator - (Rat x) { 33 LL tb = b * x.b, ta = a * x.b - b * x.a; 34 LL GCD = gcd(abs(tb), abs(ta)); 35 return Rat(ta / GCD, tb / GCD); 36 } 37 Rat operator * (Rat x) { 38 if (a * x.a == 0) return Rat(0, 1); 39 // if (b * x.b == 0) { puts("..."); while (1) ;} 40 LL tb = b * x.b, ta = a * x.a; 41 LL GCD = gcd(abs(tb), abs(ta)); 42 return Rat(ta / GCD, tb / GCD); 43 } 44 Rat operator / (Rat x) { 45 if (a * x.b == 0) return Rat(0, 1); 46 // if (b * x.a == 0) { puts("!!!"); while (1) ;} 47 LL GCD, tb = b * x.a, ta = a * x.b; 48 GCD = gcd(abs(tb), abs(ta)); 49 return Rat(ta / GCD, tb / GCD); 50 } 51 void fix() { 52 a = abs(a), b = abs(b); 53 LL GCD = gcd(b, a); 54 a /= GCD, b /= GCD; 55 } 56 } ; 57 58 struct Point { 59 LL x[3]; 60 Point operator + (Point a) { 61 Point ret; 62 for (int i = 0; i < 3; i++) ret.x[i] = x[i] + a.x[i]; 63 return ret; 64 } 65 Point operator - (Point a) { 66 Point ret; 67 for (int i = 0; i < 3; i++) ret.x[i] = x[i] - a.x[i]; 68 return ret; 69 } 70 Point operator * (LL p) { 71 Point ret; 72 for (int i = 0; i < 3; i++) ret.x[i] = x[i] * p; 73 return ret; 74 } 75 bool operator == (Point a) const { 76 for (int i = 0; i < 3; i++) if (!(x[i] == a.x[i])) return false; 77 return true; 78 } 79 void print() { 80 for (int i = 0; i < 3; i++) cout << x[i] << ' '; 81 cout << endl; 82 } 83 } ; 84 typedef Point Vec; 85 86 struct Line { 87 Point s, t; 88 Line() {} 89 Line (Point s, Point t) : s(s), t(t) {} 90 Vec vec() { return t - s;} 91 } ; 92 typedef Line Seg; 93 94 LL dotDet(Vec a, Vec b) { 95 LL ret = 0; 96 for (int i = 0; i < 3; i++) ret = ret + a.x[i] * b.x[i]; 97 return ret; 98 } 99 100 Vec crossDet(Vec a, Vec b) { 101 Vec ret; 102 for (int i = 0; i < 3; i++) { 103 ret.x[i] = a.x[(i + 1) % 3] * b.x[(i + 2) % 3] - a.x[(i + 2) % 3] * b.x[(i + 1) % 3]; 104 } 105 return ret; 106 } 107 108 inline LL vecLen(Vec x) { return dotDet(x, x);} 109 inline bool parallel(Line a, Line b) { return vecLen(crossDet(a.vec(), b.vec())) == 0;} 110 inline bool onSeg(Point x, Point a, Point b) { return parallel(Line(a, x), Line(b, x)) && dotDet(a - x, b - x) < 0;} 111 inline bool onSeg(Point x, Seg s) { return onSeg(x, s.s, s.t);} 112 113 Rat pt2Seg(Point p, Point a, Point b) { 114 if (a == b) return Rat(vecLen(p - a)); 115 Vec v1 = b - a, v2 = p - a, v3 = p - b; 116 if (dotDet(v1, v2) < 0) return Rat(vecLen(v2)); 117 else if (dotDet(v1, v3) > 0) return Rat(vecLen(v3)); 118 else return Rat(vecLen(crossDet(v1, v2)), vecLen(v1)); 119 } 120 inline Rat pt2Seg(Point p, Seg s) { return pt2Seg(p, s.s, s.t);} 121 inline Rat pt2Plane(Point p, Point p0, Vec n) { return Rat(sqr(dotDet(p - p0, n)), vecLen(n));} 122 inline bool segIntersect(Line a, Line b) { 123 Vec v1 = crossDet(a.s - b.s, a.t - b.s); 124 Vec v2 = crossDet(a.s - b.t, a.t - b.t); 125 Vec v3 = crossDet(b.s - a.s, b.t - a.s); 126 Vec v4 = crossDet(b.s - a.t, b.t - a.t); 127 // v1.print(); 128 // v2.print(); 129 // cout << dotDet(v1, v2).val() << "= =" << endl; 130 return dotDet(v1, v2) < 0 && dotDet(v3, v4) < 0; 131 }// cout << "same plane" << endl; 132 133 pair<Rat, Rat> getIntersect(Line a, Line b) { 134 Point p = a.s, q = b.s; 135 Vec v = a.vec(), u = b.vec(); 136 LL uv = dotDet(u, v), vv = dotDet(v, v), uu = dotDet(u, u); 137 LL pv = dotDet(p, v), qv = dotDet(q, v), pu = dotDet(p, u), qu = dotDet(q, u); 138 if (uv == 0) return make_pair(Rat(qv - pv, vv), Rat(pu - qu, uu)); 139 // if (vv == 0 || uv == 0 || uv / vv - uu / uv == 0) { puts("shit!"); while (1) ;} 140 Rat y = (Rat(pv - qv, vv) - Rat(pu - qu, uv)) / (Rat(uv, vv) - Rat(uu, uv)); 141 Rat x = (y * uv - pv + qv) / vv; 142 // cout << x.a << ' ' << x.b << ' ' << y.a << ' ' << y.b << endl; 143 return make_pair(x, y); 144 } 145 146 void work(Point *pt) { 147 Line a = Line(pt[0], pt[1]); 148 Line b = Line(pt[2], pt[3]); 149 if (parallel(a, b)) { 150 if (onSeg(pt[0], b) || onSeg(pt[1], b)) { puts("0 1"); return ;} 151 if (onSeg(pt[2], a) || onSeg(pt[3], a)) { puts("0 1"); return ;} 152 // cout << "parallel" << endl; 153 Rat tmp = min(min(pt2Seg(pt[0], b), pt2Seg(pt[1], b)), min(pt2Seg(pt[2], a), pt2Seg(pt[3], a))); 154 tmp.fix(); 155 printf("%lld %lld ", tmp.a, tmp.b); 156 return ; 157 } 158 Vec nor = crossDet(a.vec(), b.vec()); 159 Rat ans = pt2Plane(pt[0], pt[2], nor); 160 // cout << "~~~" << endl; 161 if (ans == 0) { 162 // cout << "same plane" << endl; 163 if (segIntersect(a, b)) { puts("0 1"); return ;} 164 Rat tmp = min(min(pt2Seg(pt[0], b), pt2Seg(pt[1], b)), min(pt2Seg(pt[2], a), pt2Seg(pt[3], a))); 165 tmp.fix(); 166 printf("%lld %lld ", tmp.a, tmp.b); 167 return ; 168 } else { 169 // cout << "diff plane" << endl; 170 pair<Rat, Rat> tmp = getIntersect(a, b); 171 // cout << tmp.first.val() << "= =" << tmp.second.val() << endl; 172 // cout << (tmp.first > 0) << endl; 173 if (tmp.first > 0 && tmp.first < 1 && tmp.second > 0 && tmp.second < 1) { 174 // cout << "cross" << endl; 175 ans.fix(); 176 printf("%lld %lld ", ans.a, ans.b); 177 } else { 178 // cout << "not cross" << endl; 179 Rat t = min(min(pt2Seg(pt[0], b), pt2Seg(pt[1], b)), min(pt2Seg(pt[2], a), pt2Seg(pt[3], a))); 180 t.fix(); 181 printf("%lld %lld ", t.a, t.b); 182 } 183 } 184 } 185 186 int main() { 187 // freopen("in", "r", stdin); 188 // freopen("out", "w", stdout); 189 Point pt[4]; 190 int T; 191 cin >> T; 192 while (T--) { 193 for (int i = 0; i < 4; i++) { 194 for (int j = 0; j < 3; j++) { 195 scanf("%lld", &pt[i].x[j]); 196 } 197 } 198 work(pt); 199 } 200 return 0; 201 } 202 203 /* 204 13 205 206 -20 -20 -20 20 20 19 207 0 0 0 1 1 1 208 209 -20 -20 -20 20 19 20 210 -20 -20 20 20 20 -20 211 212 0 0 0 20 20 20 213 0 0 10 0 20 10 214 215 0 0 0 1 1 1 216 2 3 4 1 2 2 217 218 0 0 0 0 0 0 219 0 1 1 1 2 3 220 221 0 0 0 10 10 10 222 11 12 13 10 11 11 223 224 0 0 0 1 1 1 225 1 1 1 2 2 2 226 227 1 0 0 0 1 0 228 1 1 0 2 2 0 229 230 1 0 0 0 1 0 231 0 0 0 1 1 0 232 233 0 0 0 0 0 20 234 20 0 10 0 20 10 235 236 0 0 0 20 20 20 237 1 1 2 1 1 2 238 239 0 0 0 20 20 20 240 0 20 20 0 20 20 241 242 0 0 0 0 0 20 243 20 20 0 20 20 20 244 */
——written by Lyon