解題區/解題區 - UVa

UVa 10794 - The Deadly Olympic Returns

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給你兩個三維空間的射線，請問它們的最近距離為何。

Sample Input

1
2
3
4
5
6
7
2
1
0 0 0 1 0 0
0 -1 0 0 -2 0
4
0 0 0 1 0 0
-1 0 0 -2 0 0

Sample Output

1
2
Case 1: 1.0000
Case 2: 1.0000

Solution

三分時間，因為射線的速度不一致，目前還沒有想到好的數學解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
struct Point3D {
    double x, y, z;
    Point3D(double a = 0, double b = 0, double c = 0):
        x(a), y(b), z(c) {}
    void read() {
        scanf("%lf %lf %lf", &x, &y, &z);
    }
    Point3D operator+(const Point3D &a) const {
        return Point3D(x + a.x, y + a.y, z + a.z);
    }
    Point3D operator-(const Point3D &a) const {
        return Point3D(x - a.x, y - a.y, z - a.z);
    }
    Point3D operator/(const double &a) const {
        return Point3D(x/a, y/a, z/a);
    }
    Point3D operator*(const double &a) const {
        return Point3D(x*a, y*a, z*a);
    }
    double dist(Point3D a) const {
        return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y) + (z - a.z) * (z - a.z));
    }
    double dist2(Point3D a) const {
        return (x - a.x) * (x - a.x) + (y - a.y) * (y - a.y) + (z - a.z) * (z - a.z);
    }
};
int main() {
    int testcase, cases = 0;
    double time;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf", &time);
        Point3D A, B, C, D, V1, V2;
        A.read(), B.read();
        C.read(), D.read();
        V1 = (B - A) / time;
        V2 = (D - C) / time;
        double l = 0, r = 1e+8;
        double mid, midmid, md, mmd;
        double mndist = A.dist2(C);
        while (fabs(l - r) > 1e-8) {
            mid = (l + r)/2;
            midmid = (mid + r)/2;
            md = ((V1 * mid) + A).dist2((V2 * mid) + C);
            mmd = ((V1 * midmid) + A).dist2((V2 * midmid) + C);
            mndist = min(mndist, md);
            mndist = min(mndist, mmd);
            if (md < mmd)
                r = midmid;
            else
                l = mid;
        }
        printf("Case %d: %.4lf\n", ++cases, sqrt(mndist));
    }
    return 0;
}