开发者社区> prime7> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
[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
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载