https://www.luogu.com.cn/problem/UVA1469
求空间两条线段距离，三维几何入门，存板子
1 #define IO std::ios::sync_with_stdio(0) 2 #include <bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 const double eps=1e-6; 6 ll gcd(ll x,ll y){ 7 return x%y==0?y:gcd(y,x%y); 8 } 9 struct Point{ 10 int x,y,z; 11 Point (int x=0,int y=0,int z=0):x(x),y(y),z(z){} 12 13 bool operator <(const Point &u)const{ 14 return x-u.x<0 15 ||(x-u.x==0&&y-u.y<0) 16 ||(x-u.x==0&&y-u.y==0&&z-u.z<0); 17 } 18 19 bool operator >(const Point &u)const{ 20 return u<(*this); 21 } 22 bool operator ==(const Point &u)const{ 23 return !(u<(*this)||(*this)<u); 24 } 25 bool operator !=(const Point &u)const{ 26 return !((*this)==u); 27 } 28 bool operator <=(const Point &u)const{ 29 return *this<u||*this==u; 30 } 31 bool operator >=(const Point &u)const{ 32 return u<*this||*this==u; 33 } 34 Point operator +(const Point &u)const{ 35 return Point(x+u.x,y+u.y,z+u.z); 36 } 37 Point operator -(const Point &u)const{ 38 return Point(x-u.x,y-u.y,z-u.z); 39 } 40 Point operator *(const int u)const{ 41 return Point(x*u,y*u,z*u); 42 } 43 Point operator /(const int u)const{ 44 return Point(x/u,y/u,z/u); 45 } 46 void read(){ 47 scanf("%d%d%d",&x,&y,&z); 48 } 49 }; 50 typedef Point Vector; 51 struct rat{ 52 ll z,m; 53 rat(ll z=0,ll m=1){ 54 ll d=gcd(z,m); 55 z/=d; 56 m/=d; 57 if(m<0)z=-z,m=-m; 58 this->z=z; 59 this->m=m; 60 } 61 rat operator +(const rat &u)const{ 62 ll d=gcd(m,u.m); 63 return rat(z*(u.m/d)+u.z*(m/d),m*(u.m/d)); 64 } 65 rat operator -(const rat &u)const{ 66 ll d=gcd(m,u.m); 67 return rat(z*(u.m/d)-u.z*(m/d),m*(u.m/d)); 68 } 69 rat operator *(const rat &u)const{ 70 return rat(z*u.z,m*u.m); 71 } 72 bool operator <(const rat &u)const{ 73 return z*u.m<u.z*m; 74 } 75 bool operator >(const rat &u)const{ 76 return u<*this; 77 } 78 bool operator ==(const rat &u)const{ 79 return !(u<*this||*this<u); 80 } 81 bool operator !=(const rat &u)const{ 82 return !(*this==u); 83 } 84 bool operator <=(const rat &u)const{ 85 return *this<u||*this==u; 86 } 87 bool operator >=(const rat &u)const{ 88 return u<*this||*this==u; 89 } 90 91 }; 92 93 inline int dcmp(rat u){ 94 if(u.z==0)return 0; 95 return u.z<0?-1:1; 96 } 97 ll Dot(Vector A,Vector B){ 98 return A.x*B.x+A.y*B.y+A.z*B.z; 99 } 100 ll Length(Vector A){ 101 return Dot(A,A); 102 } 103 Vector Cross(Vector A,Vector B){ 104 return Vector(A.y*B.z-A.z*B.y,A.z*B.x-A.x*B.z,A.x*B.y-A.y*B.x); 105 } 106 rat ptoseg(Point P,Point A,Point B){ 107 if(A==B)return Length(P-A); 108 Vector v1=B-A,v2=P-A,v3=P-B; 109 if(Dot(v1,v2)<0)return Length(v2); 110 else if(Dot(v1,v3)>0)return Length(v3); 111 else return rat(Length(Cross(v1,v2)),Length(v1)); 112 } 113 114 bool linetoline(Point p1, Vector u,Point p2,Vector v,rat &s){ 115 ll b=Dot(u,u)*Dot(v,v)-Dot(u,v)*Dot(u,v); 116 if(b==0)return false; 117 ll a=Dot(u,v)*Dot(v,p1-p2)-Dot(v,v)*Dot(u,p1-p2); 118 s=rat(a,b); 119 return true; 120 } 121 int T; 122 Point p[10]; 123 124 int main(){ 125 scanf("%d",&T); 126 while(T--){ 127 for(int i=1;i<=4;i++){ 128 p[i].read(); 129 } 130 rat r1,r2,ans; 131 ans.z=1e9; 132 int f1=linetoline(p[1],p[2]-p[1],p[3],p[4]-p[3],r1); 133 int f2=linetoline(p[3],p[4]-p[3],p[1],p[2]-p[1],r2); 134 135 if(f1&&f2&&r1.z>0&&r1.z<r1.m&&r2.z>0&&r2.z<r2.m){ 136 Vector u=p[2]-p[1],v=p[4]-p[3]; 137 rat x1=rat(p[1].x)+r1*u.x; 138 rat y1=rat(p[1].y)+r1*u.y; 139 rat z1=rat(p[1].z)+r1*u.z; 140 141 rat x2=rat(p[3].x)+r2*v.x; 142 rat y2=rat(p[3].y)+r2*v.y; 143 rat z2=rat(p[3].z)+r2*v.z; 144 145 ans=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1); 146 } 147 else{ 148 ans=min(ans,ptoseg(p[1],p[3],p[4])); 149 ans=min(ans,ptoseg(p[2],p[3],p[4])); 150 ans=min(ans,ptoseg(p[3],p[1],p[2])); 151 ans=min(ans,ptoseg(p[4],p[1],p[2])); 152 } 153 printf("%lld %lld ",ans.z,ans.m); 154 } 155 156 }