Easy Problem

Time limit:1000 ms   Memory limit:65536 KB
Total Submit:1755 (462 users)   Accepted Submit:366 (332 users)

Description

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).

Input

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].

Output

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

Sample Input

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

Sample Output

Case 1: 1.00
Case 2: 0.71
Case 3: 1.00

Problem Source

The 32nd ACM-ICPC Beijing First Round Internet Contest

其实和二分差不多,划个函数曲线出来,分三段,比划一下就很容易理解了:)

#include <iostream>
#include 
<cmath>
using namespace std;

double dist(double l[], double r[]) {
    
return sqrt((l[0]-r[0])*(l[0]-r[0])+(l[1]-r[1])*(l[1]-r[1])+(l[2]-r[2])*(l[2]-r[2]));
}


int main() {
   
// freopen("1024.in", "r", stdin);
    int n, cas=0;
    
double l[3], r[3], p[3], p1[3], p2[3], d1, d2;
    scanf(
"%d"&n);
    
while (n--{
        scanf(
"%lf%lf%lf%lf%lf%lf%lf%lf%lf"&p[0], &p[1], &p[2], &l[0], &l[1], &l[2], &r[0], &r[1], &r[2]);
        
while (dist(l, r) > 1e-4{
            p1[
0= (l[0+ r[0]) / 2;
            p1[
1= (l[1+ r[1]) / 2;
            p1[
2= (l[2+ r[2]) / 2;
            p2[
0= (r[0+ p1[0]) / 2;
            p2[
1= (r[1+ p1[1]) / 2;
            p2[
2= (r[2+ p1[2]) / 2;
            d1 
= dist(p1, p); d2 = dist(p2, p);
            
if (d2 >= d1) {
                r[
0= p2[0]; r[1= p2[1]; r[2= p2[2];
            }
 else {
                l[
0= p1[0]; l[1= p1[1]; l[2= p1[2];
            }

        }

        printf(
"Case %d: %.2lf\n"++cas, dist(p,l));
    }

}