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 <cmath>
#include <iostream>
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);
  }
}