CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
这一题太特殊了，所有运算都要在分数下进行，因此把完整代码贴出来。原有的模板需要做一点修改。
由于分数类敲 sqrt 比较麻烦，因此所有距离计算的是是平方后的值（见注释中的原模板和修改之后的代码）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fraction
{
ll num,den;
Fraction(ll n=0,ll d=1):num(n),den(d)
{
d=__gcd(num,den),num/=d,den/=d;
if(den<0)num=-num,den=-den;
}
friend Fraction operator+(const Fraction& A,const Fraction& B)
{
ll d=__gcd(A.den,B.den);
return Fraction(B.den/d*A.num+A.den/d*B.num,A.den/d*B.den);
}
Fraction& operator+=(const Fraction &c)
{
return *this=*this+c;
}
Fraction operator-()const
{
Fraction r(*this);
return r.num=-r.num,r;
}
friend Fraction operator-(const Fraction &a,const Fraction &c)
{
return -c+a;
}
Fraction& operator-=(const Fraction &c)
{
return *this=*this-c;
}
friend Fraction operator*(const Fraction& A,const Fraction& B)
{
return Fraction(A.num*B.num,A.den*B.den);
}
Fraction& operator*=(const Fraction &c)
{
return *this=*this*c;
}
friend Fraction operator/(const Fraction& A,const Fraction& B)
{
return Fraction(A.num*B.den,A.den*B.num);
}
Fraction& operator/=(const Fraction &c)
{
return *this=*this/c;
}
friend Fraction operator%(const Fraction &a,const Fraction &c)
{
return Fraction(a.num*c.den%(c.num*a.den),a.den*c.den);
}
Fraction& operator%=(const Fraction &c)
{
return *this=*this%c;
}
friend bool operator==(const Fraction &a,const Fraction &b)
{
return a.num*b.den==a.den*b.num;
}
friend bool operator!=(const Fraction &a,const Fraction &b)
{
return !(a==b);
}
friend bool operator<(const Fraction &a,const Fraction &b)
{
return a.num*b.den<a.den*b.num;
}
friend bool operator>(const Fraction &a,const Fraction &b)
{
return b<a;
}
friend bool operator<=(const Fraction &a,const Fraction &b)
{
return !(a>b);
}
friend bool operator>=(const Fraction &a,const Fraction &b)
{
return !(a<b);
}
friend Fraction abs(Fraction f)
{
if(f.num<0)f.num=-f.num;
return f;
}
friend ostream& operator<<(ostream &os,const Fraction &f)
{
return !f.num?os<<0:
f.den==1?os<<f.num:
os<<f.num<<'/'<<f.den;
}
};
typedef Fraction lf;
const lf EPS=1e-9,INF=1e9;
int sgn(lf d)
{
return (d>EPS)-(d<-EPS);
}
struct Coord3
{
lf X,Y,Z;
Coord3(lf X=0,lf Y=0,lf Z=0):X(X),Y(Y),Z(Z) {}
friend bool operator!=(const Coord3 &a,const Coord3 &b)
{
return sgn(a.X-b.X)||sgn(a.Y-b.Y)||sgn(a.Z-b.Z);
}
friend bool operator==(const Coord3 &a,const Coord3 &b)
{
return !(a!=b);
}
Coord3& operator+=(const Coord3 &b)
{
return X+=b.X,Y+=b.Y,Z+=b.Z,*this;
}
friend Coord3 operator+(Coord3 a,const Coord3 &b)
{
return a+=b;
}
Coord3& operator-=(const Coord3 &b)
{
return X-=b.X,Y-=b.Y,Z-=b.Z,*this;
}
friend Coord3 operator-(Coord3 a,const Coord3 &b)
{
return a-=b;
}
Coord3& operator*=(lf d)
{
return X*=d,Y*=d,Z*=d,*this;
}
friend Coord3 operator*(Coord3 a,lf d)
{
return a*=d;
}
friend Coord3 operator*(lf d,Coord3 a)
{
return a*=d;
}
Coord3& operator/=(lf d)
{
return X/=d,Y/=d,Z/=d,*this;
}
friend Coord3 operator/(Coord3 a,lf d)
{
return a/=d;
}
};
struct Line3
{
Coord3 p,v;
Line3(Coord3 p=Coord3(),Coord3 v=Coord3()):p(p),v(v) {}
Coord3 point(lf t)const
{
return p+v*t;
}
};
lf Dot(const Coord3& A,const Coord3& B)
{
return A.X*B.X+A.Y*B.Y+A.Z*B.Z;
}
Coord3 Cross(const Coord3& A,const Coord3& B)
{
return Coord3(A.Y*B.Z-A.Z*B.Y,A.Z*B.X-A.X*B.Z,A.X*B.Y-A.Y*B.X);
}
lf norm(const Coord3& A)
{
return Dot(A,A);
}
/*
lf DistanceToLine(Coord3 P,Coord3 A,Coord3 B)//点P到直线AB的距离
{
Coord3 v1=B-A,v2=P-A;
return abs(Cross(v1,v2))/abs(v1);
}
*/
lf Distance2ToLine(Coord3 P,Coord3 A,Coord3 B)//点P到直线AB的距离
{
Coord3 v1=B-A,v2=P-A;
return norm(Cross(v1,v2))/norm(v1);
}
/*
lf DistanceToSeg(Coord3 P,Coord3 A,Coord3 B)//点到线段的距离
{
if(A==B)return abs(P-A);
Coord3 v1=B-A,v2=P-A,v3=P-B;
if(sgn(Dot(v1,v2))<0)return abs(v2);
if(sgn(Dot(v1,v3))>0)return abs(v3);
return fabs(DistanceToLine(P,A,B));
}
*/
lf Distance2ToSeg(Coord3 P,Coord3 A,Coord3 B)//点到线段的距离
{
if(A==B)return norm(P-A);
Coord3 v1=B-A,v2=P-A,v3=P-B;
if(sgn(Dot(v1,v2))<0)return norm(v2);
if(sgn(Dot(v1,v3))>0)return norm(v3);
return abs(Distance2ToLine(P,A,B));
}
bool LineDistance3D(Coord3 p1,Coord3 u,Coord3 p2,Coord3 v,lf& s)//求异面直线 p1+s*u与p2+t*v的公垂线对应的s，如果平行|重合，返回0
{
lf b=Dot(u,u)*Dot(v,v)-Dot(u,v)*Dot(u,v);
if(!sgn(b))return 0;
lf a=Dot(u,v)*Dot(v,p1-p2)-Dot(v,v)*Dot(u,p1-p2);
return s=a/b,1;
}
Coord3 getCoord3()
{
ll x,y,z;
return scanf("%lld%lld%lld",&x,&y,&z),Coord3(x,y,z);
}
int main()
{
int t;
for(scanf("%d",&t); t--;)
{
Coord3 A=getCoord3(),B=getCoord3(),C=getCoord3(),D=getCoord3();
lf s,t,ans=INF;
if(LineDistance3D(A,B-A,C,D-C,s)&&0<s&&s<1&&
LineDistance3D(C,D-C,A,B-A,t)&&0<t&&t<1)
ans=norm(Line3(A,B-A).point(s)-Line3(C,D-C).point(t));
else
{
ans=min(ans,Distance2ToSeg(A,C,D));
ans=min(ans,Distance2ToSeg(B,C,D));
ans=min(ans,Distance2ToSeg(C,A,B));
ans=min(ans,Distance2ToSeg(D,A,B));
}
printf("%lld %lld\n",ans.num,ans.den);
}
}