10355 Superman

題目說明

有一個超人，他要在一個空間座標中從A點飛到B點，但在空間座標中有n個球形的汙染區域 要求讀取測資到EOF 對於每一個測資，第一行會輸入超人的名字 第二行給6個數字，前三個代表起點座標，後三個代表終點座標 第三行有一個數字n代表汙染區域的個數 接下來n行代表n個汙染區域，每一行都包含四個數字，前三個代表汙染區域的中心，第四個代表半徑。

解題過程

球體在空間座標的函數為(x-a)^2+(y-b)^2+(z-c)^2=r^2 直線可以用動點(bx+kvx,by+kvy,bz+kvz)表達 其中bx,by,bz代表起點座標，vx,vy,vz代表直線的向量(以終點-起點距離計算)，k則是一個變數，我們要算出當動點停在球面上時k的值，再反推回動點座標，進而求出直線中，在球體內的長度。 將動點代入球體函數展開時，會得到一個一元二次方程式，透過公式解得到k1及k2(分別對應兩個直線與球的交會點) 最後再考慮到起點或終點在汙染區內的可能( k<0 or k>1) 用這個計算公式計算每一個球，並加總直線在球內的長度，算出總和長度/路徑長100，再處理浮點數即可 輸出要求針對每一個側資都輸出兩行，第一行輸出超人名字，第二行輸出要通過汙染區的距離跟總距離的比例

考點:高中數學:空間座標與方程式

程式碼

#include <iostream>
#include <cmath>
using namespace std;
double dis(double bx, double by, double bz, double ex, double ey, double ez, double a, double b, double c, double r) {
    double vx = ex - bx, vy = ey - by, vz = ez - bz;
    double A = vx*vx + vy*vy + vz*vz;
    double B = 2 * ((bx - a) * vx + (by - b) * vy + (bz - c) * vz);
    double C = (a - bx) * (a - bx) + (b - by) * (b - by) + (c - bz) * (c - bz) - r * r;
    if (B * B - 4 * A * C <= 0)
        return 0;//superman don't go in poison area
    double n = sqrt(B * B - 4 * A * C);
    double k1 = (-B + n) / 2 / A, k2 = (-B - n) / 2 / A;
    k1 = max(0.0, k1);
    k2 = max(0.0, k2);
    k1 = min(1.0, k1);
    k2 = min(1.0, k2);//superman start or end in poison area
    double kq = k1 - k2;
    return sqrt((kq * vx) * (kq * vx) + (kq * vy) * (kq * vy) + (kq * vz) * (kq * vz));
}
int main() {
    string s;
    while(cin >> s) {
        cout << s << endl;
        double x, y, z, a, b, c;
        cin >> x >> y >> z >> a >> b >> c;
        double k, total=0;
        cin >> k;
        for(;k ;k--) {
            double p1, p2, p3, r;
            cin >> p1 >> p2 >> p3 >> r;
            total += dis(x, y, z, a, b, c, p1, p2, p3, r);
        }
        printf("%.2f\n",total / sqrt((x - a)*(x - a)+(y - b)*(y - b)+(z - c)*(z - c))*100);
    }
}