如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
这一题太特殊了，所有运算都要在分数下进行，因此把完整代码贴出来。原有的模板需要做一点修改。
由于分数类敲 sqrt 比较麻烦，因此所有距离计算的是是平方后的值（见注释中的原模板和修改之后的代码）。
#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);
}
}