首页 > 代码库 > HDU 4617

HDU 4617

题目多读几次就明白了。主要是求异面直线的距离,然后用距离和两圆半径之和作比较。

空间直线的距离d=|AB*n| / |n| (AB表示异面直线任意2点的连线,n表示法向量,法向量为两条异面直线方向向量的叉积,|n|表示模。

 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MAXN=50;const double eps=1e-8;struct point {	double x,y,z;};struct line {	point a,b;	double r;};int n;point tmp[3]; line le[MAXN];point vectical;point operator - (const point &a, const point &b){  //减法 	point t;	t.x=a.x-b.x; t.y=a.y-b.y; t.z=a.z-b.z;	return t;}point operator ^ (const point &u, const point &v){  //叉乘 	point t;	t.x=u.y*v.z-v.y*u.z; t.y=u.z*v.x-u.x*v.z; t.z=u.x*v.y-u.y*v.x;	return t; }point operator + (const point &a, const point &b){	point t;	t.x=a.x+b.x; t.y=a.y+b.y; t.z=a.z+b.z;	return t;}double operator *(const point &a, const point &b){	return a.x*b.x+a.y*b.y+a.z*b.z;}double dist(point &a, point &b){	double tx=a.x-b.x; double ty=a.y-b.y; double tz=a.z-b.z;	return sqrt(tx*tx+ty*ty+tz*tz);}double len (point &t){	return sqrt(t.x*t.x+t.y*t.y+t.z*t.z);}int main(){	int T;	scanf("%d",&T);	while(T--){		scanf("%d",&n);		for(int i=0;i<n;i++){			for(int j=0;j<3;j++)			scanf("%lf%lf%lf",&tmp[j].x,&tmp[j].y,&tmp[j].z);			le[i].a=tmp[0];			vectical=(tmp[1]-tmp[0])^(tmp[2]-tmp[0]);			le[i].b=le[i].a+vectical;			le[i].r=dist(tmp[1],tmp[0]);		}		bool flag=false;		double ans=1e10;		for(int i=0;i<n;i++){			for(int j=0;j<n;j++){				if(i!=j){					vectical=(le[i].a-le[i].b)^(le[j].a-le[j].b);					point tt=le[i].a-le[j].a;					double dd=fabs((tt*vectical))/len(vectical);					if(dd<=le[i].r+le[j].r){						flag=true;						break;					}					else ans=min(ans,dd-le[i].r-le[j].r);				}			}			if(flag)break;		}		if(flag) printf("Lucky\n");		else printf("%.2lf\n",ans);	}	return 0;}