# HDU 4617 立体几何-空间直线距离

+关注继续查看

#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;
}


[LintCode] 最多有多少个点在一条直线上
1 /** 2 * Definition for a point. 3 * struct Point { 4 * int x; 5 * int y; 6 * Point() : x(0), y(0) {} 7 * Point(...
575 0
POJ 2082(最大连续矩形面积)
Terrible Sets Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 2428   Accepted: 1215 Description Let N be the set of all natural numbers {0 , 1 , 2 , .
541 0
+关注