题目描述

在这个问题中，我们需要计算在给定的卫星位置和热带低气压目标位置的情况下，有多少个热带低气压目标可以被卫星击中。卫星和目标的位置都以三维坐标表示，并且我们假设地球是一个中心在原点，周长为 40,000 公里的球体。

解题思路

1. 计算地球半径：根据给定的地球周长计算地球半径。
2. 计算卫星的视线角度：对于每个卫星，计算其到地球中心的距离，并根据地球半径计算其视线角度。
3. 判断目标是否在视线内：对于每个目标，计算其到卫星的距离，并根据余弦定理计算卫星与目标之间的夹角。如果该夹角小于卫星的视线角度，则目标在卫星的视线内。
4. 统计可击中的目标数量：遍历所有目标，统计在视线内的目标数量。

代码实现

#include <bits/stdc++.h>
using namespace std;

const double pi = acos(-1.0);
const double radius = 20000.0 / pi;

struct P {
    double x, y, z, angle;
} satellite[128];

// 计算点 (x, y, z) 到原点的距离
double dist(double x, double y, double z) {
    return sqrt(x * x + y * y + z * z);
}

// 判断点 (x, y, z) 是否在卫星的视线内
bool judge(double x, double y, double z, int k) {
    for (int i = 0; i < k; ++i) {
        double a = dist(x, y, z); // 目标到地球中心的距离
        double b = dist(satellite[i].x, satellite[i].y, satellite[i].z); // 卫星到地球中心的距离
        double c = dist(satellite[i].x - x, satellite[i].y - y, satellite[i].z - z); // 卫星到目标的距离

        // 根据余弦定理计算卫星与目标之间的夹角
        double tmp_angle = acos((a * a + b * b - c * c) / (2 * a * b));

        // 如果夹角小于卫星的视线角度，则目标在卫星的视线内
        if (tmp_angle < satellite[i].angle)
            return true;
    }
    return false;
}

int main() {
    int k, m;
    while (scanf("%d%d", &k, &m) == 2) {
        if (k == 0 && m == 0)
            break;

        int cnt = 0;

        // 读取卫星位置并计算视线角度
        for (int i = 0; i < k; ++i) {
            scanf("%lf%lf%lf", &satellite[i].x, &satellite[i].y, &satellite[i].z);
            satellite[i].angle = acos(radius / dist(satellite[i].x, satellite[i].y, satellite[i].z));
        }

        // 读取目标位置并判断是否在视线内
        for (int i = 0; i < m; ++i) {
            double x, y, z;
            scanf("%lf%lf%lf", &x, &y, &z);
            if (judge(x, y, z, k))
                ++cnt;
        }

        printf("%d\n", cnt);
    }
    return 0;
}

复杂度分析

1. 时间复杂度：对于每个测试用例，读取卫星和目标位置的时间复杂度为 $O(k + m)$，判断每个目标是否在视线内的时间复杂度为 $O(k \times m)$，因此总的时间复杂度为 $O(k \times m)$。
2. 空间复杂度：代码中使用了固定大小的数组 satellite 来存储卫星位置，因此空间复杂度为 $O(k)$。

注意事项

1. 精度问题：在计算距离和角度时，由于浮点数运算的精度问题，可能会导致一些误差。在本题中，题目要求误差不超过 $10^{-8}$ 公里，因此在计算过程中需要注意精度控制。
2. 边界情况：需要考虑卫星和目标位置的边界情况，例如卫星和目标是否在地球表面上，以及卫星和目标之间的距离是否为零等。