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.样例输入30 0 0 0 1 0 1 1 01 0 0 1 0 1 1 1 0-1 -1 -1 0 1 0 -1 0 -1样例输出Case 1: 1.00Case 2: 0.71
Case 3: 1.00
题意：
为在一条线段上找到一点，与给定的Ｐ点距离最小。很明显的凸性函数，，用三分法来解决。dist函数即为求某点到P点的距离。注意精度问题。
代码：
#include<iostream>#include<cstdio>#include<cmath>#define eps 1e-8using 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;elsel=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;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
我们一直在旅行，一直在等待某个人可以成为我们旅途的伴侣，
