解題區►解題區 - 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;
}