buaa 1033 Easy Problem(三分)(简单)

作者：Gausst松鼠会 | 2024-04-10 18:35:47

踩

buaa 1033 easy problem

Easy Problem

时间限制：1000 ms | 内存限制：65536 KB
描述
In this problem, you're to calculate the distance between a point P(xp, yp, zp) and a segment (x1, y1, z1) ? (x2, y2, z2), in a 3D space, i.e. the minimal distance from P to any point Q(xq, yq, zq) on the segment (a segment is part of a line).

输入
The first line contains a single integer T (1 ≤ T ≤ 1000), the number of test cases. Each test case is a single line containing 9 integers xp, yp, zp, x1, y1, z1, x2, y2, z2. These integers are all in [-1000,1000].

输出
For each test case, print the case number and the minimal distance, to two decimal places.

样例输入
3
0 0 0 0 1 0 1 1 0
1 0 0 1 0 1 1 1 0
-1 -1 -1 0 1 0 -1 0 -1
样例输出
Case 1: 1.00
Case 2: 0.71

Case 3: 1.00

题意：

为在一条线段上找到一点，与给定的Ｐ点距离最小。很明显的凸性函数，用三分法来解决。dist函数即为求某点到P点的距离。注意精度问题。

代码：


#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-8
using namespace std;
 
typedef struct node
{
    double x,y,z;
}node;
node l,r,p;
 
double dist(node a,node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
 
int sgn(double a)
{
    return (a>eps)-(a<-eps);
}
 
node getmid(node a,node b)
{
    node mid;
    mid.x=(a.x+b.x)/2;
    mid.y=(a.y+b.y)/2;
    mid.z=(a.z+b.z)/2;
    return mid;
}
 
node search()
{
    node mid,midmid;
    while(sgn(dist(l,r))>0)
    {
        mid=getmid(l,r);
        midmid=getmid(mid,r);
        if(dist(p,mid)<dist(p,midmid))
            r=midmid;
        else
            l=mid;
    }
    return r;
}
 
int main()
{
    int t;node k;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>p.x>>p.y>>p.z;
        cin>>l.x>>l.y>>l.z;
        cin>>r.x>>r.y>>r.z;
        k=search();
        printf("Case %d: %.2lf\n",i,dist(k,p));
    }
    return 0;
}

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】