238
HDU 4617 立體幾何-空間直線距離
題意：給出空間裏n個圓的圓心，以及圓周上的兩個點，（其實是個光柱的一個截麵），問這個光柱的截麵原有的圓柱間最近的距離。其實也就是問經過圓心o點方向向量為這個圓麵的法向量的直線的距離減去兩個圓的半徑的最小值。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
int sgn(double x)
{
if(fabs(x)<eps) return 0;
if(x<0) return -1;
else return 1;
}
struct point3D
{
double x,y,z;
point3D(double _x = 0,double _y = 0,double _z = 0)
{
x = _x;
y = _y;
z = _z;
}
point3D operator -(const point3D &b)const
{
return point3D(x-b.x,y-b.y,z-b.z);
}
point3D operator ^(const point3D &b)const
{
return point3D(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
}
double operator *(const point3D &b)const
{
return x*b.x+y*b.y+z*b.z;
}
void input()
{
scanf("%lf%lf%lf",&x,&y,&z);
}
};
double Norm(point3D p)
{
return sqrt(p*p);
}
double calc(point3D a,point3D k1,point3D b,point3D k2)//計算兩條異麵直線的距離,分別是一點，方向向量。
{
point3D tmp = k1^k2;
return fabs(tmp*(a-b))/sqrt(tmp*tmp);
}
struct node
{
point3D o,p1,p2,f;
double d;
void input()
{
o.input();
p1.input();
p2.input();
}
void get()
{
f=(p1-o)^(p2-o);
d=Norm(o-p1);
}
} data[50];
int t,n;
void solve()
{
double m=1e30;
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
{
m=min(m,calc(data[i].o,data[i].f,data[j].o,data[j].f)-data[i].d-data[j].d);
if(sgn(m)<=0)
{
puts("Lucky");
return;
}
}
printf("%.2f\n",m);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0; i<n; i++)
data[i].input(),data[i].get();
solve();
}
return 0;
}
最後更新：2017-04-03 16:48:45