POJ 3129 How I Wonder What You Are!：點積求向量夾角

問題描述

給定若干星星坐標和望遠鏡參數（方向向量、視角角度），判斷每顆星星是否在任一望遠鏡視野內。輸出可見星星數。

解題思路

向量夾角公式：cos θ = (u·v) / (|u||v|)。星星向量與望遠鏡方向向量夾角 ≤ 視角角度，則可見。對每顆星星遍歷所有望遠鏡，若滿足條件計數並跳出。注意浮點精度，用 acos 或直接比較點積與 |u||v|cos φ。

代碼實現 (C++)

#include 
using namespace std;
struct Vec { double x, y, z; };
double dot(Vec a, Vec b) { return a.x*b.x + a.y*b.y + a.z*b.z; }
double norm(Vec a) { return sqrt(dot(a,a)); }
int main() {
    int n;
    while (cin >> n && n) {
        vector stars(n);
        for (int i = 0; i < n; ++i) cin >> stars[i].x >> stars[i].y >> stars[i].z;
        int m; cin >> m;
        vector tel(m); vector cosPhi(m);
        for (int i = 0; i < m; ++i) {
            cin >> tel[i].x >> tel[i].y >> tel[i].z >> cosPhi[i];
            cosPhi[i] = cos(cosPhi[i]); // 輸入為角度，轉 cos
        }
        int ans = 0;
        for (auto &s : stars) {
            double ns = norm(s);
            for (int i = 0; i < m; ++i) {
                double nt = norm(tel[i]);
                if (dot(s, tel[i]) >= ns * nt * cosPhi[i] - 1e-9) {
                    ++ans; break;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n * m)，n,m ≤ 500，約 2.5e5 操作。
• 空間複雜度：O(n + m)。

總結

三維向量夾角判斷，預計算望遠鏡方向向量模長與 cos(視角)，避免重複 acos 計算，提高精度與速度。