题解：UVA10794 The Deadly Olympic Returns!!!

furina_yyds · 2025-01-14 11:31:19 · 题解

题意

在空间中有两个匀速运动的导弹，给定一个时间以及各自的初始坐标和该时间时的坐标，求运动过程中的最短距离。

思路

求出相对初位置、相对速度，则答案就是原点到射线型轨迹的距离，注意是射线。

为什么导弹不受任何阻力影响？差评！

公式：\left| a - b \right|^2 = \left| a \right|^2 + \left| b \right|^2 + 2\times (a \times b)。

代码

#include <iostream>
#include <cmath>
#include <iomanip>
#include <array>

// 计算两个三维点的差
std::array<double, 3> subtract(const std::array<double, 3>& a, const std::array<double, 3>& b) {
    std::array<double, 3> result = {a[0] - b[0], a[1] - b[1], a[2] - b[2]};
    return result;
}

// 计算两个三维点的点积
double dot(const std::array<double, 3>& a, const std::array<double, 3>& b) {
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
}

// 计算两个三维点的叉积
std::array<double, 3> cross(const std::array<double, 3>& a, const std::array<double, 3>& b) {
    std::array<double, 3> result = {a[1] * b[2] - a[2] * b[1], 
                               a[2] * b[0] - a[0] * b[2], 
                               a[0] * b[1] - a[1] * b[0]};
    return result;
}

// 计算三维点的模
double mag(const std::array<double, 3>& p) {
    return std::sqrt(p[0] * p[0] + p[1] * p[1] + p[2] * p[2]);
}

// 计算叉积的模
double crossMag(const std::array<double, 3>& a, const std::array<double, 3>& b) {
    std::array<double, 3> c = cross(a, b);
    return mag(c);
}

// 计算两个三维向量的平行距离
double parallelDist(const std::array<double, 3>& B1A1, const std::array<double, 3>& d1) {
    std::array<double, 3> crossProduct = cross(B1A1, d1);
    return mag(crossProduct) / mag(d1);
}

// 计算两个三维向量的最短距离
double dist(const std::array<double, 3>& A1, const std::array<double, 3>& A2, 
           const std::array<double, 3>& B1, const std::array<double, 3>& B2) {
    std::array<double, 3> d1 = subtract(A2, A1);
    std::array<double, 3> d2 = subtract(B2, B1);
    std::array<double, 3> B1A1 = subtract(A1, B1);
    double mage = crossMag(d1, d2);
    if (mage < 1e-9) {  // 处理精度问题
        return parallelDist(B1A1, d1);
    }
    std::array<double, 3> cro = cross(d1, d2);
    return std::fabs(dot(B1A1, cro)) / mage;
}

// 输入操作
void input(std::array<double, 3>& point) {
    std::cin >> point[0] >> point[1] >> point[2];
}

// 输出操作
void output(int i, double minD) {
    std::cout << "Case " << i << ": " << std::fixed << std::setprecision(4) << minD << std::endl;
}

int main() {
    int T;
    std::cin >> T;
    for (int i = 1; i <= T; ++i) {
        std::array<double, 3> A1, A2, B1, B2;
        input(A1);
        input(A2);
        input(B1);
        input(B2);
        double minD = dist(A1, A2, B1, B2);
        output(i, minD);
    }
    return 0;
}