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
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct Point
{
double x,y,z;
};
double dis(Point a,Point b)
{
return sqrt(0.0+(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 main()
{
int ci,pl=1;scanf("%d",&ci);
while(ci--)
{
Point a[3];
for(int i=0;i<3;i++) cin>>a[i].x>>a[i].y>>a[i].z;
while(dis(a[1],a[2])>1e-4)//a[1]表示左边界，a[2]表示右边界
{
Point l,r,deta;
//三分求极值
deta.x=(a[2].x-a[1].x)/3,deta.y=(a[2].y-a[1].y)/3,deta.z=(a[2].z-a[1].z)/3;
l.x=a[1].x+deta.x,l.y=a[1].y+deta.y,l.z=a[1].z+deta.z;// 1/3
r.x=a[1].x+2*deta.x,r.y=a[1].y+2*deta.y,r.z=a[1].z+2*deta.z;// 2/3
//important dis表示函数f,以下因上凸函数和下凸函数不同而不同
//此题求点到线段距离，故是"下凸"函数
// 如果左右边界为a,b,三分点为l,r,则如果f(l)>f(r),则l左面部分可删去不用考虑,将区间减少为(l,b);
//如果f(l)<f(r),则r右面部分可删去不用考虑,将区间减少为(a,r);
//直到l和r重叠，三分结束,解为f(a)或f(b);
if(dis(a[0],l)>=dis(a[0],r)) a[1]=l;
else a[2]=r;
}
printf("Case %d: %.2lf/n",pl++,dis(a[0],a[1]));
}
return 0;
}